How to resolve "Video too large" error message with MMS video attachment
Try resolution of 320 by 240.
It is what works on my Leon.

Also... Try this...
Start a message.
Click attach.
Click from camera.
Shoot a short 10 second video.
Send the video.
Then examine the video's details ...you will see it is 320 by 240
Best regards. Hutch.