First, simple as it seems, sometimes just restarting the device will resolve the problem.
Should that not do it, when you changed over did you make sure your new plan had data? That would be necessary for sending anything attached to a text message, as it takes it from an SMS message to a multimedia message.
If your plan does include data, then you should talk to your new carrier/service provider about the problem. it may well be something on their end. They could have problems with the towers in your area, it could also be they gave you the wrong kind of SIM for your device, or it could even be on their end. Mine recently wouldn't let me get messages. Could do everything else, just not that. I had to call them up and talk to a 'few' people before I got someone who actually understood it wasn't my device, or something else and they put in a ticket on the problem. 24 hours later, worked fine. So it can't hurt to call and be insistent that it get resolved.