Two things come to mind.
First, are you sure that it's long distance that is causing the problem, or perhaps just a particular fax machine that you are calling that happens to be long distance. How many different long distance faxes (to different numbers) have you tried? Do they all fail? etc...
Second, if it is truly a long distance issue, it could be because CO's will put in echo cancelers into the path once the distance (and in turn the time delay) reaches a certain point. Fax machines don't behave well when there is an echo canceler in the path. You can however try to adjust the settings on your fax machine to help. Unfortunately it's been a few years since I had to deal with that stuff, so I can't suggest anything concrete (try another protocol if it's supported or increase the redundancy level). Needless to say, half duplex is what you want.