Sorry, but you do realise that h.264 IS mpeg4 right?
http://en.wikipedia.org/wiki/MPEG-4#MPEG-4_parts (look at part 10)
http://en.wikipedia.org/wiki/H.264
Further more, could you post some (or parts) of video's that do and do not work?
I have an iPhone 3G, and a friend of mine has a 32gig touch, sure we could test a bit for you.