I’m in the middle of a changeover from CS3 to CS4 and so still have both suites installed on my workstation.
I found that I the MP4 files I was exporting from CS4 using the iPod presets were playing in VLC ok, but were garbled in Quicktime player (started on a green frame and jumped around the timeline like a Japanese horror film). I had tried these MP4 files on both PC and Mac and with the latest Quicktime installed – but always the same.
In an act of desperation, I went to my Adobe Premiere CS3 folder, searched for all files with “mp4” in the name (included .ax and .dll files) and dumped them into the CS4 application folders (After Effects, Premiere, Adobe Media Encoder). I said yes to copy over the newer versions and the problem went away. I may have just copied over the latest MP4 algorithms for best quality and compression, but at least the files will play in Quicktime, iTunes and and ultimately my iPhone.