I assume you can upload other smaller files without problems?
Is it 1.7.9 CMS?
Could you please double check all the settings listed here How do I upload files bigger than 2MB / How can I increase the upload file size limit?
Depending on your web server, please check additional notes there as well.
When you upload the video file, I assume you waited for it to finish uploading?
Could you capture a screenshot of this error?