I switched to Vonage VOIP phone service and were not able to fax out anymore. Did some googling and it seems that there is a need to dial *99 before dialing the actual numbers. *99 prefix forces the ATA to fax/data mode. Here is the link.
Note that although it worked for domestic numbers, it is still not working for international faxes.
Update, I was able to fax international by setting resolution to “standard” on my HP Laser jet 3200. The resolution defaults to “fine”.
7/26/2011: Update, no need to dial *99 for domestic fax anymore.