I never make h264 from AE. I always render a quicktime and then export an H264 from Quicktime Pro.
I'd check how often you are setting keyframes in the compression settings... I'd set one every 30 frames or so if your video doesn't edit too quickly.
The higher they fly... the much.
My Reel: