I don't know why that's happening, but personally, I've never attempted to make H.264's in AE and I don't think your problem is that big a loss. Not at all. Here's why:
AE has NEVER been able to make really good-looking H.264 video because it can't do multipass encoding, which is a big boost to image quality. If I have to make an H.264, I render out a high-quality file from AE and use something else to do the encoding: Adobe Media Encoder, Apple's Compressor, Sorenson Video and even Quicktime Pro come immediately to mind.
Sr. Promotion Producer
KCRG-TV (ABC) Cedar Rapids, IA
I output a lot of HD Blu-ray files for our media server and found that the quality in CS5 is really bad compared to CS3 with the same settings. Not sure what happened to the encoder in CS5 but I can confirm that it has taken a turn for the worse.