Blackberry Email Woes

Everything worked great at first, but now I'm having e-mail issues with my Blackberry.

Now whenever I compose and send an e-mail I get "invalid message from server" but if I select the same e-mail and hit resend, it goes fine.

I'm using the Internet service. It checks mail on my imap server just fine and pushes it down to me.