Usually, after connecting to your VPS/Server for the first time and trying to
sudo apt install <something>
you’d get some warning such as:
perl: warning: Setting locale failed. perl: warning: Please check that your locale settings: LANGUAGE = (unset), LC_ALL = (unset), LC_CTYPE = "el_GR.UTF-8", LANG = "en_US.UTF-8" are supported and installed on your system. perl: warning: Falling back to a fallback locale ("en_US.UTF-8"). locale: Cannot set LC_CTYPE to default locale: No such file or directory locale: Cannot set LC_ALL to default locale: No such file or directory
which means you need to generate language locales.
In my case I needed the el_GR.UTF-8 locale:
sudo locale-gen el_GR.UTF-8 sudo dpkg-reconfigure locales
and the problem was gone.