In general, a terminal application like emacs -nw has only very limited information about what colors are available. The shell will have an environment variable called TERM which contains the name of the terminal you're using. The application can then use a library such as terminfo to pick the right escape sequences to use each feature of the terminal. This design reflects the historical reality that there were hundreds of different types of terminals, and that they all had different capabilities, and that even when those capabilities overlapped they had different protocols for using them.
On a modern system you will likely only ever see four different values for this variable, as modern terminals have been replaced by terminal emulators. The most common value is xterm. This represents a terminal with the least-common-denominator of features, and most importantly supports 16 colors. Most terminals also support xterm-256color which extends this to 256 colors. (The other common values screen and screen-256color aren't as important here).
In the original 16 color setup, the terminal chooses the colors (and possibly allows the user to edit the selection). In the 256 color setup the terminal still chooses the colors, but the colors are chosen to be uniformly spaced so that all hues are more or less equally well represented.
So, how does this help you? Well, you can see that the color palette is entirely up to the terminal, so you'll want to find out how to configure it (or choose a different one). The emacs theme tells emacs a 24-bit color to use, then emacs looks at the TERM variable to see how many colors are available and makes a guess as to how to best map that 24-bit color into a palette entry, then the terminal takes that palette entry and maps it back into a 24-bit color to display on your monitor. (Unless your X-Windows display is in some other color mode, but that's super unlikely these days).
Another fix would be to run emacs not in a terminal but as a normal X application. This gives it access to the full 24-bit color space, the ability to use your entire selection fonts (with anti-aliasing even), multiple font sizes, text zooming, proportional fonts and more. Just run it without the -nw.
Followup:
The basic faces (those not defined in some more specialized mode) are all defined in the lisp/faces.el source file. Here's the definition of the highlight face:
(defface highlight
'((((class color) (min-colors 88) (background light))
:background "darkseagreen2")
(((class color) (min-colors 88) (background dark))
:background "darkolivegreen")
(((class color) (min-colors 16) (background light))
:background "darkseagreen2")
(((class color) (min-colors 16) (background dark))
:background "darkolivegreen")
(((class color) (min-colors 8))
:background "green" :foreground "black")
(t :inverse-video t))
"Basic face for highlighting."
:group 'basic-faces)
Obviously you can see that when there are more than 8 colors (16-color modes have 8 colors each with a bright and dark version) it doesn't set a background color. This doesn't answer the question "why", however. You should file a bug on emacs and suggest it; you'll either find the answer or get it changed :). Use M-x report-emacs-bug to send in the bug report. Naturally, including a patch that fixes it usually gets you mad props.
