gnome-terminal unicode chars not showing - Locale is set to en_US.utf8

The solution was much simpler. I had to go to the GUI settings for gnome-terminal, visit Terminal -> Set Character Encoding -> UTF-8.

-- To keep this as the default in Ubuntu (and sorry to find out that it's a distro-specific solution in this SE forum):

gconftool --set --type=string /apps/gnome-terminal/profiles/Default/encoding en_US.UTF-8

I had the same problem with Terminal -> Set Character Encoding -> Unicode (UTF-8) correctly set. The problem was fixed by setting the encoding to something else and then back to UTF-8. The visible characters did not change right away, but newly typed started appearing correctly. No need to restart anything.