Message 171407 - Python tracker
My results aren't quite as dramatic as yours, but there does appear to be a regression:
$ ./python -V
Python 2.7.3+
$ ./python -m timeit -s "s = 'b'*1000" "s.replace('b', 'a')"
100000 loops, best of 3: 16.5 usec per loop
$ ./python -V
Python 3.3.0rc3+
$ ./python -m timeit -s "s = 'b'*1000" "s.replace('b', 'a')"
10000 loops, best of 3: 22.7 usec per loop