I get this problem a lot.

perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
        LANGUAGE = (unset),
        LC_ALL = (unset),
        LANG = "en_AU.UTF-8"
    are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").
locale: Cannot set LC_CTYPE to default locale: No such file or directory
locale: Cannot set LC_MESSAGES to default locale: No such file or directory
locale: Cannot set LC_ALL to default locale: No such file or directory

I think possibly this solves it.

$ sudo apt-get install --reinstall language-pack-en

It says comforting things like...

Generating locales...
  en_AU.UTF-8... done
  en_BW.UTF-8... done

Update: Except it didn't work. But maybe this will.

$ sudo localedef -i en_AU -f UTF8 en_AU.utf8