I can't recommend highly enough Gavin DeBecker's "Protecting the Gift" as a resource on how to prepare your children to protect themselves.
In this case, it sounds to me that these immature men saw this child "behaving weirdly" <as dad says he does sometimes> <as mom overheard the men say also> and they made a cruel inappropriate joke about the handicapped stall.
My son will be 10 next week and if he and I were traveling alone, I would have no problem bringing him into the ladies room with me; I also don't think many other women would have a problem with it. My child might die of embarrassment, though. And I wouldn't bring both my boys in the ladies room if we were all traveling together-- cause then they'd get all silly and loud, etc.