mrz:
Cash isn't necessary.
Space - as many people have said, a folding screen or something takes up hardly any room.
Staff - Helpers/volunters/parents/work placement students come in all the time in most primary schools. Even if they are in a different year they can be diverted up to the top year for 5 mins to supervise.
Other solutions: Two years doing PE together so boys can change in one room and girls in another. Or, PE can be timetabled to be last lesson, so children don't have to change at all if they don't want to. Or, children can just wear joggers or more adaptable clothing on PE days.
With a little creative thinking, it should be possible for the vast majority of schools to adapt something.
However, sorry to be rude, but you seem to embody the 'can't be bothered if I can get away with it,' school of thinking that several posters here have mentioned at their schools. The point is, it shouldn't be up to children to have to make specific requests because they are embarrassed. I could imagine it being horrifically excruciating for a 10 year old girl to have to ask her (possibly male) teacher if she can change in the toilets because she's on her period/doesn't want the boys to see her bra/is teased for having leg hair, etc.
Schools have a duty of pastoral care to children, and this includes acknowledging that today's children are going through puberty earlier than previous generations, and have a right to their privacy if they want it.
If the age for children to go into gender-specific changing rooms at swimming pools, etc, is 8, then why shouldn't this be enforced at schools too?