I'm still undecided, and I haven't played beta or anything to help solve the dilemma.

I have 4xShamans as a possibility, with any tank as a main.
I have a DK+4xRet team that I love for BGs, but it sounds like this comp is totally different in Cataclysm.
I'm levelling a 5xDruid setup, which I like in BGs for stealth plus ranged moonkin fun.

Sounds like instance running in Cata for leveling purposes will be significantly harder than any prior expansion, unfortunately. Good news is that PvP gearing should be much easier since it can be done almost exclusively through BGs.

I'm leaning towards playing the 5x Druids for flexibility's sake, and using the lead druid as my raiding main as well. Stealth plus ranged DPS is still pretty nice, and the boomkins are getting some fun new toys as well!