I'm having the same issue here. Can't for the life of me get 1920x1080 to work without the overscan issue.
I finally managed to get everything to fit on my screen with 1360x768 resolution, but it also always starts up in 1024x768. The Gnome display utility (in Ubuntu 9.04 updated today) just tells me that it can't work with the Nvidia display driver, and asks to load up the vendor controlled display utility. If I tell it YES then it just loads up nvidia-settings. If I put no, it does display the Gnome utility, but the max resolution is 1024x768.
That could be the issue right there. I'll do some further testing, but I think that with either
Option "ExactModeTimingsDVI" "TRUE"
Option "UseEDID" "False"
the driver is thinking my monitor does a max of 1024x768 (though nvidia-settings lists 1360x768 as the highest resolution.)
This has been driving me nuts since I bought my HDTV a month or so ago.
The main problem has been that every program I've tried on it tells me I have different refresh rates. X detects 29-49 Horizontal and Powerstrip said it was 15-63 or something like that. It's an RCA L42FHD37 (which from what I can tell is identical to a Tech. Concepts 42" TV that is made in China by TLC.)