What's going on is that Bash is getting confused about the number of printing characters in your prompt. It sends cursor positioning sequences to the terminal to position the cursor properly for doing command history and such. It needs to have a good idea of where the cursor actually is after printing the prompt.
Try setting your prompt to this:
It should now work as expected.
\] pairs tell Bash that the stuff between them is a non-printing escape sequence and won't actually move the cursor forward. It will then correctly guess the cursor position and do a proper replacement when going through your command history.
This information can be found in the info node
(bash)Printing a Prompt.
Edit: In newer versions of bash this has changed to
(bash)Controlling the Prompt.