Video uploaded with the native media uploader gives Error 404

Ok, I found the problem. It wasn’t a WordPress problem, but a server issue.

I had to add the file extension .mp4 with MIME type video/mp4 in the MIME types of the IIS server.

Here is the link I found with the steps to correct the issue:
http://forums.asp.net/t/1470612.aspx/1

 1) Select the site to configure in IIS, right click and select "Properties" 
 2) Under HTTP Headers Tab, select "File Types" under the MIME Map section and select "New Type" 
 3) Type ".flv" as the associated extension and "video/x-flv" as the content type or "flv-application/octet-stream" I'm not sure on which one gives here.
 4) for .mp4 files type ".mp4" as the extension and "video/mp4" as the mime type (this one I tested personally) 
 5) Select "OK",  
 6) type services.msc, find the "World Wide Web Publishing Service" and click
 on the restart icon on top or open up and choose restart