[RESOLVIDO] Eu testei para este comportamento usando o Ubuntu 11.10 live cd e não tive o mesmo problemas no terminal, então imaginei que uma mudança que eu fizesse provavelmente seria a causa.
Eu fiz algumas alterações no arquivo .bashrc ao seguir um tutorial sobre como personalizar o prompt do usuário bash, que deve ter causado esse problema.
Após restaurar o arquivo .bashrc original do backup, o problema com as linhas sobrepostas está resolvido.
Obrigado pela sua resposta Huckle. Felicidades