¿Está utilizando python 2.xo 3.0?
Si está utilizando 2.x, trate de hacer la cadena de expresión regular una cadena Unicode de escape, la 'U'. Como es regex, es una buena práctica hacer que su cadena de expresiones regulares sea una cadena sin formato, con 'r'. Además, poner su patrón completo entre paréntesis es superfluo.
re.sub(ur'[\u064B-\u0652\u06D4\u0670\u0674\u06D5-\u06ED]+', '', ...)
http://docs.python.org/tutorial/introduction.html#unicode-strings
Editar:
También es una buena práctica usar la bandera re.UNICODE/re.U/expresiones regulares para Unicode, pero sólo afecta a los alias de clase de caracteres como (u?) \ w o \ b, de los cuales este patrón no usa ninguno y por lo tanto no se vería afectado por.
Hmm, no sabe que podría concatenar tanto '' '' u'' y prefijos r''. ¡Eso es muy bonito! –