A simple first step would be to pick a known good fax number and do some testing. I would first call it from a cellular phone as a control and make sure you get a fax tone. Then try to send to that number from the fax machine behind the ATA. If that fails, I would take a test set and plug in to the ATA and call the same number from the test set. If the call succeeds on the test set and you hear a fax tone, the issue is with the fax machine configuration/compatibility. If the call fails, the issue is with your CUCM (or whatever call agent you use), your dial plan, the PSTN, etc.
