i did this at 60 on my warlock, and getting rep back is easy you can just do thise tunin quests

http://www.wowwiki.com/Quest:Traitor_to_the_Bloodsail
http://www.wowwiki.com/Quest:Mending_Old_Wounds
http://www.wowwiki.com/Quest:War_at_Sea
http://www.wowwiki.com/Quest:Making_Amends