well naga specifically are enemies of both alliance and horde arent they?
Yep
Honestly, the only real alternatives for new races I see are Nerubians (Simular enviroments to dwarves, simular loss as humans, anti-Undead if you ignore the fact they're pure evil. Unlikely to join with Horde due to Forsaken), Goblins (A cartel who works only with that faction as opposed to the Steamwheedle Cartel, who work with both), Furbolgs (Could actually work on the Horde if you say its the Northrend Furbolgs coming to get some vengence on the Dwarves, otherwise plenty of other furbolgs to use for Ally), Murlocs(Random tribe around Maelstrom or something. Smarter than they appear and a fan favourite), Makura for either (See Murlocs but without the fan favourite part. Anti-Naga, so will probably at least be a group) and out of them, Goblins is the only one I would even consider still in the running
Oh, and Brad, this patch Blizzard added helmets for goblins. Now they just need a lot of variations and they'd be perfect as playable characters. They're also the only race in this topic which has been seriously CONSIDERED to be a new race, but they lost to gnomes
I predict that the next one will be South Seas, allowing for Undermine, Nazjatar, that troll capital city island, Pandaria, all sorts of places. I see Emerald Dream coming out later, considering that one of its portals comes out into Northrend, and it also is fairly boring and generic all around, not full of different enviroments like Outlands