I telnet'ed to a Unix system and then back to my laptop (Mac).
Started Emacs -nw and it came up in the terminal.
I get the same list for list-color-display that you got. I have a
black menu with white text at the top. My mode lines are black with
white. My normal text is black on white background. The *scratch*
butter starts with a "red" messages on white background.
All of these are muted slightly... the red is not full on and the
write is very slightly grey. But it sounds like your grey is darker.
My guess is the terminfo on Ubuntu is not exactly compatible with
Mac's Terminal.app... but that seems rather unlikely.
My second guess is Ubuntu has modified emacs in this area but that
also seems unlikely.
I don't know enough about how the colors and faces all interact or how
to customize them. Hopefully someone else on this list will pipe up.