Terminal com codificação incorreta

Boa tarde, nunca vi este problema, mas instalei um Ubuntu Server (Máquina Virtual) e os caracteres não estão corretos como segue abaixo:

Construindo �rvore de depend�ncias       

Lendo informa��o de estado... Pronto

Calculando atualiza��o... Pronto

Os pacotes a seguir ser�o mantidos em suas vers�es atuais 

Já realizei alguns procedimentos, comandos, etc. Mas nada resolveu, alguém pode me ajudar?