I have my gmail account setup w/the native pop3 app...not sure if its the same as what would be downloaded from Nokia w/Nokia Mail, like I did w/ my girl's e71.

Maybe there is something wrong w/the SMTP server settings, or outgoing server credentials/authentication type? Were you ever able to send before?