Confirmed working Ally to Horde. Here are the steps that I took . Now granted I had ZERO rep with them before changing.
1. Did all the quests including the turn in rep to get the 42000 rep.
2. Faction Changed.
3. Went to Karynaku to get the "Zuluhad the Whacked" quest.
4. Killed Zuluhead released the dragon and then went and turned in "Ally to the Netherwing". This yielded another 42000 rep.
Here are pic:
http://img16.imageshack.us/f/wowscrn...410142831.jpg/
http://img541.imageshack.us/i/wowscr...410143003.jpg/
http://img137.imageshack.us/i/wowscr...410143015.jpg/
I hope this is a bit more thorough then some of the posts here on how to do this. Pictures included.