Edit your .bashrc as follows. Before the "case $TERM" statement that sets color_prompt, add the following:
# GNOME Terminal is broken re: $TERM settings
if [ "$COLORTERM" = "gnome-terminal" -a "$TERM" = "xterm" ]; then
TERM="xterm-256color"
fi
Now edit that "case $TERM" statement to look like this: