"So when exactly did this problem start? I have been in the beta and haven't seen a difference"
It started at the launch of the new video apps. The beta dashboard worked great, but then the new video layer seems to have been activated at the launch of the new Netflix and Hulu apps, hours before the dashboard came out of beta. Now with the new video layer active, it effects every source of video that I have seen on the 360. Dropping HDMI reference level from Standard to Intermediate fixes video black levels, but then breaks game black levels. For example, hopping in to Battlefield 3 last night to check out the new Karkand expansion, I had to bump Brightness up from it's 50% level to about 75% to avoid all shadows from just being a deep dark pit of detail-less despair.
You have the black level problem. If you don't see it, then awesome! Doesn't change the fact that it is there, on your systems.