Coloque as seqüências de formatação em colchetes com escape para informar ao terminal que esses caracteres não são realmente impressos (para cálculos de largura):
PS1='\[\e[0;36m\]\u \W: \[\e[m\]';
Mais detalhes aqui na seção Cores .
Editado para vincular ao envio original no Meta, já que quem o copiou para o Blog.SU bagunçou praticamente tudo.