This problem isn't terribly common anymore, but it still happens often enough to be irritating.
There is a small possibility that the voice portion of the circuit is being transported via IP somewhere along the way. If so, faxing will be sketchy unless the carrier supports the emerging T.38 standard. But that's a stretch; I'm convinced that the trouble is due to DSL service being shared on your voice-grade line.
I've tried using
ferrite chokes on the line cord (to supress any noise introduced by the fax machine), which got me nowhere. I like
dexman's idea, which may help if the DSL signal is a little on the hot side.
Customers that experience this problem will also sync up at the lowest BPS rate if using a modem instead of a fax.