Note to self
Si este error no se arregla con sudo dpkg-reconfigure locales hay que modificar a mano el archivo /etc/default/locale y agregar las variables que no tienen valor. Puedes ver las variables relevantes con el comando locale
Mi archivo /etc/default/locale se ve así:
LANG=en_US.UTF-8
LANGUAGE=en_US.UTF-8
LC_CTYPE=en_US.UTF-8