If you're getting "setting locale failed" messages when you're doing an upgrade on a newly-installed server, the cause is as it says - there isn't a locale to set.
So, you need to set a locale.
sudo locale-gen en_US.UTF-8 sudo dpkg-reconfigure locales
If the install has been configured to use another locale, such as en_GB (you'll see it in the message), use that instead.