Weird symptoms within my network

My company has a WAN all using CISCO routers with models vary from 1700, 2600 and 3640 and has a Linux as a mail server. All branch connected using Frame Relay, and the strange thing is my users in branch have a problem with sending mail but there is no problem with receiving e-mails. It is obvious if you have problem with sending you might also having a problem receiving e-mail. If you have the similar problem that I have, would you please share with me. By the way, my Firewall engine is Watchguard FireboxII.