I agree, it sure sounds like a clocking issue.
I would confirm that the GSM is really using the CO clock not an internally generated clock.
I would also try claling into the system and listen for a peridoci (as in every so often) click. If you can hear it then tim eit. If it happens at a regular interval then you defintley have two clocks that are not synchronised.
As I reality check you might try a different fax machine. I saw a situation once with a modem that for some reason would lose it on certian PBXes. As the manufacturers we couldn't really tell what was goign on other than the fact that the modem processor load was peaking out periodically for no reason, only on these PBXes (in other words it was not a simple case of bad noise or frequency response impairments).
If another fax machine works it MAY be possible that the current fax machine has some hidden menu options that cusotmer support could have you change. Of course investigate the clocking issue first.
Good luck.