I don't have Illustrator on this computer, so sorry if this is a bit vague, but I would guess at something like the following:
1. Select each circle, and go to Object > Expand.
2. With everything selected, use the 'Union' pathfinder to turn it all into one shape with no strokes.
3. Using the direct selection tool, select each segment you want. Go to Object > Compound Path > Release, and now you should be able to color it in.
If it doesn't work, I'll have a look at it again after the weekend and get you a proper answer. I think the principle should be ok though (expand the strokes and release the compound paths)