I've had a lot more success, running 2's as Frost.

The first week, while I was still in the honor grind gearing up process, I offered gold per win for a "pvp god" to help an "average frost DK with xxxx res" get to the Conquest cap for the week.

Double DPS has worked a lot better than pairing with a healer.
Mainly because lacking a strong weapon, the DPS is a little short.
Anything stuck in melee range, I would go with the Obliterate priority sequence.
Anything that can run away, I would go with the Howling Blast priority sequence.

My best partner has been Frost Mages, and after that Fury Warriors.
I never lasted that long, against two DPS when partnered with a Stealth partner.

The only games double melee consistently loses, is against Frost Mage + another DPS.
Teams that are 1x DPS, 1x Heals, are fairly easy if you focus on the melee toon, especially if you Strangulate/MindFreeze/Hungering Cold the healer, and if your partner has anything of that sort too.

Three weeks of wins, and the Conquest weapon will make a huge impact.
The stats for the Axe, Mace and Sword are identical in every way.
My gnomes have no edge with one weapon type over another (bonuses with 1 Handers)... I think the sword looks best.
Other races might have a bonus with one type over another.