Your Alliance character will need to open up Mechagon Island (up to making the dailies available).
I did all the achievements & rep on this character. Then I took my Worgen Hunter and opened up the island. She was then able to do the recruitment quest.