legal situations span juristictions, and there is an actual legal precedent in this matter. You actualy are meant to follow the legal "Principle of least astonishment". a person who presents as a woman will be less astonishing using the women's restroom than the men's  

In Human Resources its meant to run like this

Transgender / Transsexual Bathroom - Restroom References

In landmark case Cruzan vs Davis, a ruling was made in June 2002 by a federal appeals court in Minnesota that an employer is within its rights to instruct a transgendered employee to use the restroom matching their new presentation, and that if another employee complains, the company may offer the complaining employee an accomodation (such a the use of a different restroom by the complaining employee.) .