Why does CTRL-r act weirdly (showing only part of a command) on OS X
Solution 1:
You probably have escape sequences for colors in your prompt that are not properly delimited. They need to be enclosed in \[ and \].
PS1='\[\033[1;36m\]\u\[\033[0m\]@\[\033[1;34m\]\h\[\033[0m\]\$ `
The length of non-printing character sequences are not included in the length of the prompt when they are thus enclosed and the position of previous commands needs to be calculated for proper display when they wrap.