I'm afraid I can't help you there because I use Final Cut
Studio to make my mp4s and it works beautifully. But then it would
because it's a native format for QuickTime.
One thing you might try is getting the full version of QT Pro
for the PC (I assume your on a PC) and use QT to export as mp4.
It's really cheap. Only £20 and well worth having. Once it's
loaded on your system you should even see it in your export options
straight from Premiere if I remember correctly. It's been years
since I made the switch to Mac. It's worth having it as an option
on your system anyway.
http://store.apple.com/Apple/WebObjects/ukstore.woa/wa/RSLID?mco=A326C C89&nplm=D3381
Hope this helps. I followed the tutorial and everything
worked just fine. Good luck.
Mark