First you chose what your gender will be and customize the look. When done, Click accept and talk to the Make-Over-Mage again. Then your client will freeze. You have to close it and re-open another client. Log back in and go back to design your character. Now you can chose the other gender and customize it.
You will now have beard or whatever on your girl character or have smexy hair and skirt on your guy character.