I got my replacement ATV2 today. As I expected, it did not help. I immediately returned it to the Apple Store.
I believe most of our guesses thus far have been correct: The ATV2 is not negotiating properly with the sink (the TV) what resolution it is capable of putting out. It's OK that it only does 720p, it is just not saying so to the TV when it gets the EDID information from the TV. Older TVs capable of 480i/480p/720p/1080i are probably defaulting to 1080i (or something other than 720p) in the absence of this information.
The form factor of the digital input is a red herring and just something Apple latched on to avoid addressing the problem:
http://www.hdmi.org/learningcenter/faq.aspx#31
I'm the original poster of this question, and I'm done for now. I will continue using my Roku + ATV1 for the time being. If anyone wants to rattle some chains, I think one of the best avenues of attack might be to get the HDMI working group to poke Apple, since they are using the HDMI trademark to brand their product and that implies adhering to ... something.