I have been using the program gtop to show all sorts of nice stats in a neat graph format in the terminal, but on some of the machines it just shows a ? instead of the . or bars.

Here's how I fixed it.

sudo dpkg-reconfigure locales

Then I selected my locale "en_AU UTF-8"

After doing that, and rebooting (I really wish I didn't have to do that!) it works as it should!

Thanks to the guys on ##linux on freenode for pointing me in the right direction.

Hopefully this helps someone else!