WARNING! Your environment specifies an invalid locale. This can affect your user experience significantly...

Hi everyone, just finished trying a new instance of ubuntu, first time logging in and got the following notification :

Changing password for root.
(current) UNIX password:
Enter new UNIX password:
Retype new UNIX password:
_____________________________________________________________________
WARNING! Your environment specifies an invalid locale.
 This can affect your user experience significantly, including the
 ability to manage packages. You may install the locales by running:

   sudo apt-get install language-pack-UTF-8
     or
   sudo locale-gen UTF-8

To see all available language packs, run:
   apt-cache search "^language-pack-[a-z][a-z]$"
To disable this message for all users, run:
   sudo touch /var/lib/cloud/instance/locale-check.skip
_____________________________________________________________________

Did try the following command :

   sudo apt-get install language-pack-UTF-8
     or
   sudo locale-gen UTF-8

But still nothing happened, each time I’m installing a package, still invoking the same warning. Any clues what had happened?

Thanks,