when I last played with faxing from PDAs, I found that not all mobile phones are proper fax devices - some require a lot more work on the connected computer.
I'll have to try and remember the details, it's been a while.
I think if you use minicom to connect over the serial/ir, and ask "AT+FCLASS?" you get the phone's fax class, and it needs to be 2.0 or 2.1?
Sorry to be vague.