Well, I'm a janitor (at my university) and I end up cleaning both men's and women's restrooms regularly.
Like sensei, I have also experienced the odd "women's pre-restroom" phenomenon. It's easily understandable why women go to the restroom in packs when the restroom has the most comfortable seats in the building.
Whenever the restrooms have differing color schemes, the women's restrooms are brighter. I suppose there might be an obscure reason for it; I know that the bright yellow "Restroom Closed" signs I put up seem to attract women like swarming flies.
As for women's restrooms being "clean"... well, that takes effort. On average, I find that when I get to cleaning restrooms, the women have seriously trashed the place relative to the men's room. Seriously.