Have you checked your e-mail account settings? Usually when using external accounts (POP3, IMAP, etc.) there might be different settings you need for incoming and outgoing messages (server names, ports, username, password, security type). If you're CERTAIN those are correct, then the outgoing server might be having issues.
If you're using GMail, however, this shouldn't be a problem if you're using the stock GMail app and you're able to receive e-mails (and, of course, the e-mail you're replying to is a valid one).