i assume that you are running this from your house, or work. i would check the outside ports to make sure they are open. i have heard that line before yes port 25 is open but the person that you are talking to knows nothing other then what is on the monitor in front of them.
to check your ports you can use this site
if port 25 is blocked you can use a relay service to send mail out on port 2525
this is how i have to do it sucks having to pay for a service but what are you going to do.