Although surrounding the escapes with \x01 and \x02 worked to correctly remove the message while doing a reverse-i-search (thus preserving the original line), the input line measurement still appears to be incorrect as demonstated with the following actions:

[steve@localhost ~]$ python
Python 2.7.5 (default, Nov 12 2013, 16:18:42) 
[GCC 4.8.2 20131017 (Red Hat 4.8.2-1)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import sys
>>> sys.ps1 = '\x01\033[32m>>> \033[0m\x02'
>>> # on the next line, press the up arrow to get this line and then backspace, over the entire prompt
... 
#<-- backspaced up until here
... 


...again, not a big deal, just annoying when deleting word with a repeated 'alt+backspace' or ctrl+w