I had the same issue the first time I turned on my new replacement xbox and I have solved it. Yes it is the "handshake" in a manner of speaking. If you go into the Display settings there is an option called "Display Discovery" which is apparently turned on by default. If you're running through a AVR, Surround Sound, a HDMI switch, or if your TV is just goofy, this discovery will not be able to complete the handshake with The TV as it does not have that direct connection. For whatever reason, Microsoft decided in this scenario that the best thing to do is default to DVI mode...WRONG. Anyway, just turn this feature off, it will tell you it needs to restart, do the restart, and you should hear the warm, comforting "vwoing" sound we are all so used to hearing, and it should default to 1080p. You may have to turn your Audio settings back to Dolby Digital after this change. I think I did.
I too Created an account just to say i love you and that you are amazing! I was freaking out for a bit there haha!