Вы используете Python 2.x или 3.0?
Если вы используете 2.x, попробуйте сделать строку regex строкой с escape-символом Unicode, используя 'u'. Так как это регулярное выражение, хорошей практикой является сделать строку регулярного выражения необработанной строкой с помощью 'r'. Кроме того, указание всего шаблона в скобках является излишним.
re.sub(ur'[\u064B-\u0652\u06D4\u0670\u0674\u06D5-\u06ED]+', '', ...)
http://docs.python.org/tutorial/introduction.html#unicode-strings
Edit:
Также рекомендуется использовать флаг re.UNICODE / re.U / (? U) для регулярных выражений Юникода, но он влияет только на псевдонимы классов символов, такие как \ w или \ b, для которых этот шаблон не использует так не будет затронуто.