You don't mention how the cleaners moved about on the roof. It sounds like they walked directly on the tiles. If that's the case, you will probably see more tiles come off the roof.
When you said, "So we have a 50 year Monier tile roof that is 5 years old." Did you mean these were recycled tiles. It's also possible that some of these tiles got cracked upon the initial removal or the re-install.
I'd bring in a roofing company that wasn't associated with the cleaning company by getting other estimates.
I don't think you can assign blame without having watched them crawl all over the roof.
Ron

Sorry to hear about your situation. If the cleaning company is not willing to admit any responsibilty, which is very likely in any case, you may have to go to small claims court to collect. If you do that you will have to have a very strong case with evidence of negligence on their part, not coincidence in the event. You probably don't have photos of them working on the roof or witnesses. I would do what Ron says and hire a roofing company to inspect the roof. There may be other tiles ready to come down and/or they may be able to detect damgage and assess the cause more accurately. They may be able to tell if the cracks are from footprints or other causes.

Thanks guys,

Yes, they walked on the roof; how else are they going to clean it? The roof was installed new when the house was built in 2003 and has a 50 year warranty (materials only) so I hope none of the material is "recycled". I'm still waiting to hear back from the 1st roofing contractor who was sent out to inspect by the cleaning company last week. I would not want to go to small claims court as it will of course be a question as to whether the cleaning was what loosened the tile that fell off or if it was already loose. Thanks for the tips!

Tile roofs, like slate roofs should never be walked on directly. You have a few options that will preserve the integrity of these roofs. Ladders that hook over the ridge and plywood that disperses the weight over an area that doesn't compromise structure. But that takes time and material and most homeowners have no idea about it, so they don't do it.
The problems arise over time so they can deny responsibility.
Ron

DO NOT have just any old roofing company work on your roof. Absolutely get a roofing company that specializes in tile roofs out to look at yours. If you get any old joe schmo to do the fix, the odds are good that they won't know about the peculiarities of tile. When replacing tiles, one absolutely must reuse the same nail holes. If one doesn't, they you risk holes in the sheathing and future water damage. In 2005, we had a 6' x 6' square of tile removed and reinstalled to replace a leak in the sheathing and the cost then was $1800.

Do yourself a favor and get a specialist to give an estimate.

Posted by home_decorator_guy:"Yes, they walked on the roof; how else are they going to clean it?"

You don't walk directly on the roof.

So you saw them walking on the roof then? And did not stop them?

You better have it inspected now and repaired before problems from the damage get worse.