"Invalid file type: video" in default video block

I’m out of ideas how to solve this one.

I’m using the default Block/Video, and want to upload an mp4 to the site. I can upload an image to the same area fine. I can select the mp4, but get an invalid file type message.