I've just struggled with the same issue... and this helped me fix/reset locales:

sudo dpkg-reconfigure locales