I am currently running a 70 rogue/pally team (Not entirely recommended but it does still work). Another team I have started is a Druid/Rogue which has a few better benefits such as both can stealth, the Druid can tank, heal, or DPS with my rogue and the synergy isn't bad either. However, even with both teams I run I still want to try a Rogue/Shaman group. Though the Shaman won't be able to stealth and thus make certain things easier, however things like Windfury totem may bring a better aspect to the table for the Rogue.

So to answer your question, I would suggest either the Druid or Shaman as a pair for your Rogue. Hope that helps a little. Just my two cents.