The issue might very well be strictly related to GNU readline.

I have both successfully reproduced it in a C program:

#include <stdio.h>
#include <readline/readline.h>
int main() {
        readline("\x1b[31;1mthis is a bold red prompt\x1b[m> ");
}

gcc -lreadline test.c

and found a fix, hinted at by this stackoverflow post:
http://stackoverflow.com/questions/9468435/look-how-to-fix-column-calculation-in-python-readline-if-use-color-prompt

Readline uses the characters \x01 and \x02 to mark invisible portions of the prompt, so I am now pre-processing the prompt with this function:

def surround_ansi_escapes(prompt, start = "\x01", end = "\x02"):
        escaped = False
        result = ""

        for c in prompt:
                if c == "\x1b" and not escaped:
                        result += start + c
                        escaped = True
                elif c.isalpha() and escaped:
                        result += c + end
                        escaped = False
                else:
                        result += c

        return result

However, in my opionion this fact deserves at least to be mentioned in the readline documentation.