The thing is, those "solid colors" in your desktop background list are actually graphics files stored in /Library/Desktop Pictures/Solid Colors. They are only 128x128 pixels in size.
So, either the contents of that folder are damaged or (more likely) something's happened to damage your preferences. Personally, I'd try deleting ~/Library/Preferences/com.apple.desktop.plist and see if that solves the problem.