If the console isn't letting you change the setting, you probably need to set the physical output to HD. The A/V plug on the back of the system actually has a switch on it. If it's set to TV, then it's locked at 480i and the system won't let you change it. If you switch it to HDTV, it will unlock the other resolutions.
It should tell you this right on the screen in the system settings. When you go to the "Display" portion of the System blade, there should be a message saying "HD output is disabled because your A/V is set to 'TV'" or something to that effect, with a small picture of the cable indicating the location of the switch.