This is the error. It comes up when I paste and enter the installation code (which I get from the Package Control website) and each time I open up Sublime Text.
Your system's locale is set to a value that can not handle non-ASCII characters. Package Control can not properly work unless this is fixed.
On Linux, please reference your distribution's docs for information on properly setting the LANG environmental variable. As a temporary work-around, you can launch Sublime Text from the terminal with:
I had the same problem with Ubuntu 13.04 so it's probably not version-dependent.