I've leveled a Warrior Priest combo and had no problem at all.

To be honest I just used to charge in with the Warrior and then play him as usual, while using macro's to simply SW:P then Wand, and also a couple of macro's to throw Renew\Flash\Greater Heals when necessary.

I've found it no trouble at all, especially now Prot has been changed up I had a ton of fun usually going through 3 or 4 mobs at a time, with minimal downtime. Just stock up on + DMG\Healing gear for the priest, and dont worry about any other stats (I never ran out of mana unless I had a mega pull with some adds)

Dont give up yet