The H.264 format only permits a limited, constrained set of frame sizes. In After Effects CS4, these constraints were communicated in the Comments field of the H.264 Export Settings dialog box, and you must follow those instructions or else get the error message that you got.
In After Effects CS5, if your settings don't match one of the sets of settings allowed by the H.264 specification, then a warning icon in the Output Module Settings dialog box appears, and After Effects tells you what it's going to do to make the video fit.
The F4V format (which contains video encoded using H.264) has a different set of constrained sizes, including the 1920x1080 size that you're looking for. And other formats (like QuickTime) aren't constrained in this way at all. So, you might have better success choosing a different output format, if you need that output frame size.
You may have choosen the wrong level. Try using level 4.1 or 4.2 (4.1 is the one used by BluRay specs) for your 1920x1080 output. Also be sure to have a standard framerate like 23,96 / 24 / 25 / 29,97.