O que está acontecendo é que o Bash está ficando confuso sobre o número de caracteres de impressão no seu prompt. Ele envia seqüências de posicionamento do cursor para o terminal para posicionar o cursor corretamente para fazer o histórico de comandos e tal. Ele precisa ter uma boa idéia de onde o cursor está, na verdade, após a impressão do prompt.
Tente definir seu prompt para isso:
PS1='\[\e[35m\][\W]:\[\e[0m\] '
Agora deve funcionar como esperado.
Os pares \[
e \]
informam ao Bash que o material entre eles é uma seqüência de escape não imprimível e não move o cursor para frente. Em seguida, ele adivinhará corretamente a posição do cursor e fará uma substituição adequada ao passar pelo histórico de comandos.
Essas informações podem ser encontradas no nó de informações (bash)Printing a Prompt
.
Editar: Em versões mais recentes do bash isso mudou para (bash)Controlling the Prompt
.