Had this on my iMac after updating to Mavericks, first i thought my Thunderbolt to DVI adapter was broken, but that was not the case.
The displays settings for the external Samsung monitor under older OSX used to show resolutions like 1920x1080 and 1600x900. After resetting everything it will query the external monitor and make a fresh table of supported resolutions, and in my case added 1080p and 720p (instead of 1920x1080 and 1280x720). Here are the steps i used (from memory).
Removed all custom colorsync profiles
Like /library/colorsync/profiles/S22B300 as well as from ~/library/colorsync/...
and also others like /system/library/colorsync/... if any.)
Removed /library/preferences/com.apple.windowserver.....
also from ~/library/preferences/byhost/com.apple.windowserver....
Zap PRAM (and choose startup disk)
Restart and hold CMD-ALT-P-R untill second startup chime.
(In case you have a different startup disk than the default one,
after the chime press ALT to choose your startup disk,
and set system-preferences startupdisk after boot.)
regards,
GDmac