Fax by phone problems - some thoughts.
Are you using the phone as a modem, i.e. you send fax from a computer via its fax program, or are you using it as a Fax machine, whereby you configure your phone as a fax machine, a phone utility which does not apply to all hand phones ? Have you confirmed that the "modem" is a data/fax modem ?
Also, the phone's modem connection would be very very slow - 5-10 Kbps, or lower ? Perhaps the fax machine at the other end was just waiting for the data then timed out ?