khanadil,
This is a little bit old so maybe fixed already but I just had a similar problem and fixed it by checking the CLAN nic on the Call Pilot server and making sure that there were correct entries for the DNS server and DNS suffix in the TCPIP properties. Mine had nothing so I entered the info and have been faxing ever since.
If that doesn't help, from a PC that has desktop messaging, open up CPTrace and initiate a fax and then copy and paste the CPTrace here.