CSApprox (GitHub: godlygeek/csapprox) by Matt Wozniski can be used to convert gVim colour schemes to work with 256 colour terminals. Many people now use 256 colour terminals, so if you use CSApprox with schemes that previously looked bad you should see something much closer to the right colours.
Whenever you change colorschemes using the :colorscheme command this script will be executed. It will take the colors that the scheme specified for use in the GUI and use an approximation algorithm to try to gracefully degrade them to the closest color available in your terminal. If you are running in a GUI or if your terminal doesn't support 88 or 256 colors, no changes are made. Also, no changes will be made if the colorscheme seems to have been high color already.
Versions of Vim after 7.3 don't need GUI support for CSApprox to work, so if you've got a modern version of Vim on a server without X then you should be able to see the colours you expect.