I second ONQ's observation- that the travertine needs to be well supported.
Travertine tiles are by their nature quite brittle and crumbly, especially if left in the cold and rain for any period of time. Your problem could be the tile, but without proper support, the tile can easily develop fault lines with heavy traffic and disintegrate.
By support, i mean that the adhesive underneath needs to be applied correctly by the installer (tiler) so that no big cavities are present underneath the tile. Porcelain and Ceramic tiles can live with less adhesive underneath, but not travertine, especially thin slabs.
If you want to see evidence of this happening on a large scale, just pop along to a certain large Dublin shopping mall (named after a river) and you will see that parts of the floor there are suffering the same fate. Many tiles have been replaced since it was built and they're still not 100%.
Maybe that is your problem. Maybe not..