Are you using the standard message app?
If so, its probably down to an incorrect APN settting. MMS messages don't use the same sending settings as sms as mms uses the data network rather than gsm.
What carrier are you? You should be able to check with them what their apn settings are (or should be).