I recently came across solarized. I started to use it immediately for vim and mutt, but after a few days the low contrast of the color scheme started to annoy me. Oh and btw, I’m red/green color blind.
I went searching and found “xoria256” a color scheme suited for 256 color
terminal and a dark background. There is even a Ubuntu/Debian package
for it: vim-scripts. Unlike solarized it doesn’t come with a custom palette, just
use Tango in gnome-terminal (or whatever your favorite is).