I had this issue too and after searching the internet I came across the answer. It has something to do with the type of screen you're using and how computer's interpret images compared to a TV. So, if you're connected to a TV, and you are connected through a native HDMI plug, as in no DVI to HDMI adapter or such then make sure that you go into Catalyst Center for ATI or NVIDIA control center and verify that it is 1080p 59.94Hz (if you have 1080p of course). Then go into Windows Media Center and run the TV set up portion that's found in Tasks under the general tab. Choose flat panel as your TV type. Then you must run all the way through the different setting controls, including color, contrast, etc for it to save your setting. After you've done this and go back to the main menu it should fix it.
Now if you have a DVI connection or use the adapter, then that takes a little bit of patience. I had to adjust the scale of the desktop screen in order to see the desktop but when it came time for the windows media center I had to put it back to the full 1080p setting which overscaned on my TV making my desktop larger than the screen was. So make sure your Windows Media Center icon is in the center of the desktop so you can find it. Then start WMC up again.
After getting into Windows Media Center, go into the Tasks area again and into General, then TV set up or whatever. Choose flat panel again. The difference is that it will detect that strange resolution and ask if you want to keep it. Say no and proceed to the next screen and select the output that says 1080p. Somehow it figures it out and it works. Remember to go through the same settings for the rest of the stuff, even if you don't change anything. That's about all I can remember. It's a pain in the butt I know but it has a lot to do with the old overscan stuff leftover from standard definition days. Hope this helps and it still might take a little bit of playing around to get it right.