Make sure you have mobile data, MMS will not send without active mobile data. There is also the possibility that it is too large, but I think the messaging app will resize it automatically, but I'm not 100% on that one.
How are you attaching the pic? Was it taken with the Lumia's camera? I've never had issues sending pics taken with the camera, and they don't seem to be resized. I start by opening the pic, then tapping the 3 dots on the lower right of the screen to bring up options - choose Share, then Messaging... it opens a text message with the pic attached.
Are you having any other problems with calls, texts, browser, etc?