Change language Ubuntu Server 16

[bcqqp]

I have a fresh VPS deployed with Ubuntu server 16.04 and unfortunately it's deployed with Dutch language. I need to switch this to English language for root user and all future (new) users but all my efforts to switch it over seem to fail. Can someone please explain how to change the language?
What I already tried (all commands work without errors):

sudo locale-gen en_US.UTF-8
sudo dpkg-reconfigure locales
sudo update-locale LANG=en_US.UTF-8
restarting server multiple times


My current locale output:

root@server:~# locale
LANG=nl_NL.utf8
LANGUAGE=nl_NL.utf8
LC_CTYPE="nl_NL.utf8"
LC_NUMERIC="nl_NL.utf8"
LC_TIME="nl_NL.utf8"
LC_COLLATE="nl_NL.utf8"
LC_MONETARY="nl_NL.utf8"
LC_MESSAGES="nl_NL.utf8"
LC_PAPER="nl_NL.utf8"
LC_NAME="nl_NL.utf8"
LC_ADDRESS="nl_NL.utf8"
LC_TELEPHONE="nl_NL.utf8"
LC_MEASUREMENT="nl_NL.utf8"
LC_IDENTIFICATION="nl_NL.utf8"
LC_ALL=nl_NL.utf8

root@server:~# locale -a
C
C.UTF-8
en_US
en_US.iso88591
en_US.utf8
nl_NL.utf8
POSIX


.profile contents:


# ~/.profile: executed by Bourne-compatible login shells.

if [ "$BASH" ]; then
if [ -f ~/.bashrc ]; then
. ~/.bashrc
fi
fi

mesg n || true


/etc/default/locale contents:

# File generated by update-locale
LANGUAGE=en_US
LANG=en_US.UTF-8
LC_MESSAGES=POSIX
var=locale

/etc/environment contents:

PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games"

Some messages seem to be in English, like this error message:

root@server:~# asjkldfhgasajksgdsad
-bash: asjkldfhgasajksgdsad: command not found

and some messages are in Dutch, like #date or #apt:

root@server:~# date
wo 23 mei 2018 15:51:02 CEST
root@server:~# apt
apt 1.2.26 (amd64)
Gebruik: apt [opties] commando

apt is pakketbeheerdersgereedschap voor de commandoregel dat beschikt
over commando's voor het zoeken en beheren van pakketten en voor het
opzoeken van informatie over hen. Het biedt dezelfde functionaliteit
als de gespecialiseerde gereedschappen van APT, zoals apt-get en
apt-cache, maar maakt standaard gebruik van opties op een manier
die beter aan interactief gebruik aangepast is.


EDIT: even though I selected en_US at the end of the dpkg-reconfigure locales script, I had to manually unselect Dutch in the first step of the script so it's completely deleted. This forces it to English but now whenever I login to my console it says:

-bash: warning: setlocale: LC_ALL: cannot change locale (nl_NL.utf8)
The freaking #locale command also keeps presenting me the Dutch settings:


root@server:~# locale
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
LANG=nl_NL.utf8
LANGUAGE=nl_NL.utf8
LC_CTYPE="nl_NL.utf8"
LC_NUMERIC="nl_NL.utf8"
LC_TIME="nl_NL.utf8"
LC_COLLATE="nl_NL.utf8"
LC_MONETARY="nl_NL.utf8"
LC_MESSAGES="nl_NL.utf8"
LC_PAPER="nl_NL.utf8"
LC_NAME="nl_NL.utf8"
LC_ADDRESS="nl_NL.utf8"
LC_TELEPHONE="nl_NL.utf8"
LC_MEASUREMENT="nl_NL.utf8"
LC_IDENTIFICATION="nl_NL.utf8"
LC_ALL=nl_NL.utf8

root@server:~# update-locale LANG=en_US.UTF-8
perl: warning: Setting locale failed.
perl: warning: Please check that your locale settings:
LANGUAGE = "nl_NL.utf8",
LC_ALL = "nl_NL.utf8",
LC_MESSAGES = "POSIX",
LANG = "nl_NL.utf8"
are supported and installed on your system.
perl: warning: Falling back to the standard locale ("C").

This is driving me absolutely insane. Why is it so hard to change the language.