Do you want to export just the .mp4 as a file on its own?
Or are you trying to export the presentation as an .mp4 showing the video running within the presentation?
If the former, you can extract the .mp4 (or any media) via the Finder.
Find your .key file, Ctrl-Click it and select 'View Package Contents'. This will open a window showing the contents of the .key file, including a Data directory. In this directory are the raw images, movies, audio files, etc. that are used in the presentation. You can just copy the file out of there to any other location on your desktop. Maybe not as streamlined as saving it from inside Keynote itself, but not overly complex.
FWIW, the Export -> Movie option is designed to save a movie version of your presentation playback, not to export individual pieces of media, which is why it doesn't work as you expect here.