A mesma coisa aconteceu comigo. Com base no que Thomas disse acima, eu fui capaz de consertar isso removendo o comentário de en_US.UTF-8 UTF-8
no meu arquivo /etc/locale.gen
(anteriormente nenhuma das linhas tinha sido comentada), então executando locale-gen
.