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.