Since Honolulu uses the 2006 IBC, which references the 2003 ANSI A117.1, I'm going to reference the 2010 ADA Standards, since it is more current.
Section 213.2 states, "Where toilet rooms are provided, each toilet room shall comply with 603" (Emphasis mine). There is an exception that allows the use of a unisex toilet room in lieu of making each toilet room accessible, but that exception only applies to alterations and historic buildings.
Therefore, to answer your question: if two restrooms (mens and womens) are provided, both are required to be accessible, with one accessible water closet in an accessible toilet compartment, and one accessible lavatory. Toilet accessories in the accessible toilet compartment and common toilet accessories (i.e., soap dispensers, towel dispensers, waste receptacles, and mirrors) are required to be accessible.