I have a similar problem, although I'm using Ubuntu 6.10 and the Driver 1.0-9361. The only thing i additionally found out so far is that you have to use Option "ModeValidation" "DFP-0: NoDFPNativeResolutionCheck"
instead of NoEdidDFPMaxSizeCheck
, since it's no longer availiable according to the Driver Readme. This should remove the black borders on at least 3 sides (in my case).
My problem history is explained at http://www.nvnews.net/vbulletin/showthread.php?t=84773