Hay un error en python 2.x eso solo es python 3.x fijo. De hecho, este error está incluso en iconv de OS X (pero no en glibc).
Esto es lo que está pasando:
Python 2.x no reconoce los pares sustitutos de UTF8 [1] como no válidos (que es lo que es su secuencia de caracteres)
Esto debería ser todo lo que se necesita:
foo.decode('utf8').encode('utf8')
Pero gracias a ese error que no están solucionando, no detecta los pares sustitutos.
Pruebe esto en python 2.x y luego en 3.x:
b'\xed\xbd\xbf'.decode('utf8')
Lanzará un error (correctamente) en este último. Tampoco lo están arreglando en la rama 2.x. Consulte [2] y [3] para obtener más información
[1] https://www.rfc-editor.org/rfc/ rfc3629#sección-4
[2] http://bugs.python.org/issue9133
[3] http://bugs.python.org/issue8271#msg102209
