One other thing to note here was a problem I used to have when moving my Xbox between TVs. The problem I found was caused by some (older) HDTVs not displaying 1080p output. Therefore you have to return your TV to an 1080p compliant set and reduce the resolution down to 720-1080i; then you can try it again with the TV you were initially trying to work it on.
An alternative fix, if your can't do the above step, is to call someone who has an Xbox and get them to shout out instructions in how to reach this menu 'blind' (right 6 times, down 2 times, press a, etc etc). As long as you can hear your Xbox 'blooping' then you will be able to do this.
I don't think that this is the problem that B3asti3 had, but is here for future reference in case anyone else thinks their TV/Xbox is playing up.