I had the same problem and thats because most ISP's do not allow relaying through their systems. You need to reconfigure your outgoing mail server to smtp.vzwmail.net you'll probably have to set up an account first on the vzwmail website first. Then you must put in your user name which is your mobile number like this
2015551212@vzwmail.net and the password and whether or not you want to save it.
Hope that helps...if not, you can always call Verizon, they were very helpful, but for the price we are paying for their service....they should be!