Cannot Fax from PC

I cannot get a laptop on a client's network to Fax to an HP 6310A-I-O printer. One PC on the network faxes fine and the other cannot, it can print, and all other functions work, but faxing from this PC does not work. 
When I look at the Event Viewer-Application I get the following two errors:

========================================
Event Type: Warning
Event Source: Microsoft Fax
Event Category: Initialization/Termination 
Event ID: 32068
Date: 2/24/2006
Time: 8:43:47 AM
User: N/A
Computer:
Description:
The outgoing routing rule is not valid because it cannot find a valid device. The outgoing faxes that use this rule will not be routed. Verify that the targeted device or devices (if routed to a group of devices) is connected and installed correctly, and turned on. If routed to a group, verify that the group is configured correctly. Country/region code: '*' Area code: '*'

For more information, see Help and Support Center athttp://go.microsoft.com/fwlink/events.asp.
===========================================
Event Type: Warning
Event Source: Microsoft Fax
Event Category: Initialization/Termination 
Event ID: 32026
Date: 2/24/2006
Time: 8:43:47 AM
User: N/A
Computer:
Description:
Fax Service failed to initialize any assigned fax devices (virtual or TAPI). No faxes can be sent or received until a fax device is installed.

For more information, see Help and Support Center athttp://go.microsoft.com/fwlink/events.asp.
==========================================

There is no modem installed, I've uninstalled the drivers and software and reinstalled. No dice. I've stuck and don't know where to go next. Anyone have a problem like this before?