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`