I have been having a similar problem and want to share what I have learned by reading this thread and messing around with some video files. I use Nero recode to recode mpg2 --> mpg4 (h.264) using the standard iPod/iPhone profile supplied by Nero. These files all play flawlessly on my video iPod and did play on the previous version of iPhone software. I purchased iPhone 3G and none of the video files played and I got the same error "THIS MOVIE FORMAT IS NOT SUPPORTED".
It explicitly says on the Apple site that h.264 is supported on iphone 3G, so i figured there was some small glitch that was causing the problem. I was able to do two things to get the old movies to play, and to get new movies encoded in Nero to play without manipulation:
1. With files that were previously encoded I used the "convert to ipod/iphone function in itunes, or imported into QT pro and exported as iphone .m4v, both solutions worked. The itunes solution seems better because you can highlight multiple files and just let it go... i did two full length movies last night and they converted and played with no problem (and they still play on ipod as well).
2. I examined the specs for the supported h.264 on the Apple website and noticed some subtle differences in that and the specs for the nero profile. In particular, nero defaults to 640x476 screen size and 29.97 fps frame rate. Apple states that iphone supports 640x480 and 30 fps. So I made these simple changes to the nero profile and voila... newly encoded video in nero recode played with no problem (also on ipod). I did not need to manually enable de-interlace or motion adaptive as stated above.
My conclusion is that Steve changed something in the codec to make it less lenient, and now the files have to strictly conform to the screen resolution and frame rate or they will not work. I too hope that this is fixed with an update, but for now I think these two solutions can help the Nero people anyway.