Another thing to try (I hear this is fairly common for some reason) is to see if the MMS firewall on your device is enabled for some silly reason -- I had this issue with SMS a little while back.
Go to Options > Security Options > Firewall
If the box next to MMS is checked, uncheck it, then test to see if MMS is working.
If that doesn't resolve your issues, call your carrier.
Good luck.