This has nothing to do with the file being of type mp4 and everything to do with the video codec being used. If you have video files that are not playing particularly well on the tablet, you should consider looking at Handbrake, a free piece of software that allows you to convert video formats. In-depth instructions are available at How to: Handbrake and A500 on xda-developers.
Basically, you want to use the following settings in the application:
- Load your video in Handbrake
- Picture tab - set Anamorphic to Loose and Width to 1280
- Video tab - Select Constant Quality with a value of 20
- Audio tab - Audio Codec AAC(faac), Mixdown Dolby Pro Logic II, Samplerate Auto, Bitrate 160, DRC 0.0
There are some settings that can be tweaked in the Advance tab (see the forum post I linked). You can then save this profile in Handbrake and run this for any video files you encounter.
For playback on the Iconia, I use Mobo Player but there are others that work fine.