Hi Jodie, have you checked and made sure your APN settings are correct? Settings -> Wireless & Networks -> Mobile Networks -> Access Point Names?
Also, you could try clearing the cache and data associated with the message app, Settings -> Applications -> Manage Applications -> All -> Messaging -> Clear Cache/Data.
Be aware that clearing the data associated with it might mean you lose your messages though.