I ran into the same problem hooking the RPi up to my 1080p HDTV.
The solution I used was to add a line to the configuration file. I added hdmi_mode=4 to the end and it scaled back the resolution. eLinux.org has a whole list of options available to set the resolution to your liking.
http://elinux.org/RPi_config.txt