Here's your issue. This server has the same exact leveling rates at pre-Wrath. That means these rates are higher than launch BC rates! For me it's quite fast in comparison to what I expected. First quest on my druid I hadn't even completed it and I hit L1. That was normally done upon completing the turn-in of the first quest on live BC. I normally went around killing extra mobs to get L1 before turning the quest in back then. I'd think that if Warmane's BC servers have their XP rates set by the patch prior to the following expansion then the Wrath servers are the same. Meaning you're used to Cata XP for leveling. Hate to say, but that ruined leveling for you. I spent a month hitting 70 on my second character, a hunter, in BC. I'd been 60 in Vanilla on the druid so I rolled right through the Dark Portal.
Again I think pre-Cata leveling was spoiled for you. That's rough because I enjoy seeing the entirety of a zone's quests. I leveled a second druid in Wrath. I have to say I did it in half the time of the hunter. And I didn't care because my goal was to raid with two healers that had left my BC guild for another server.
Word of advice, switch to ret!!! You can tank dungeons are ret for quite a while. Prot pally leveling is a pain! I leveled one in BC. All I can say is I regret it and it ruined the class for me for years. The only tank that can level in its tank spec quickly is a feral. Prot pallies and warriors are horrible unless you can chain dungeons and even with these rates you can't do that. Feral has the luxury of also being a dps tree...yay, when we were actually hybrids! lol Heck, I have a leveling build for maximum damage done, but with more tanking talents and skipping one or two required dps talents. You did pick one of the rougher classes to level too. :/