Your setup should work. I just wonder whether you don't have your Priest kicking in too early. If you die often because the priest took aggro from the Warrior, you might want to just make him DoT, or start DPSing later.

I ran a Fury Warrior + Paladin duet for a while, it was great fun, and I basically never died. Paladin was only healing though.