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!