A clarification here is due: mp4 is the contasiner format (not the codec) . An mp4 extension may mean anything inside it. Maybe you could post here which codecs are inside your mp4 file (e.g. mpeg2, vorbis..).
You can see them by playing the same clip with Totem and enabling the sidebar.
Also, try rebooting... I've had some problems where I play something that works fine, then do something else and come back and try and play it again and it's not a recognized format. A reboot sorts it out.
the main problem seems to be the chapter makers with the meta data of movies files, its a strange one but a definate bug.
but like the others have said it could be a number of things, you could try downloading kmplayer, the ui is rubbish but it plays everything the stock media player moans about.
