Try registering the phone again by dialing *228 option 2. Also you might have to go into your BIS account and send the service books again. Is this a new phone? It sounds like it might not have fully set itself up.
I can receive messages on my Blackberry curve from my gmail account, however, I cannot reply to the message. It says that I do not have a messaging service setup. How do I fix this?
On your device, go to Options>Advanced Options>Default Services. You should have two things here: Calendar (CICAL) and Messaging (CMIME). The calendar entry does not really matter for this, but the messaging should be set to your email@example.com email address. If it is not, change it and save. Then, your sending emails should work.