Yeah, with ret paladins being ridiculously good (I haven't met anything else that can solo my 5 level 80 shamans), I can imagine having 1 prot or holy and 4 ret would be insane.

I've been running 1 holy paladin, and 4 blood DKs for a few weeks, and I've also played around with having rogues. Multi-boxing melees is not as bad as it initially seems. You do get follow broken from combat (but also get that with channeled spells and various other abilities from non-melee) so you either want to hit a follow key religiously or use Jamba; personally I use a follow key to follow on demand. There's a mess of abilities for some classes -- warriors with stances come to mind -- that you will have to plan for, but for the most part you can just create one key to spam attacks. My DKs do /castrandom between several abilities for example, or there's /castsequence, etc. Other than that, positioning is the only thing you have to worry about, which is a matter of running your lead a little past the mob in some cases so the follower(s) can be in melee range, and re-following during combat if adjustment is needed.