On my gmail accounts the fix I found was you have to setup your outgoing SMTP server to sprint, and set your outgoing server login to your sprint mail username and password. You can call up sprints tech support and they can give you the settings/walk you through setting it up. Gmail is slow sending, but it works great!
Edit: Here are my settings:
Outgoing SMTP Server : smtp.sprintpcs.com
Outgoing Server Login:
user: smtp.sprintpcs.com\dmcniel08
password: password