У меня была такая же проблема в Eclipse Luna 4.0.4 с Python 3.4.1 и PyDev 3.6.0.Я попробовал шаги, описанные выше, и несколько других, но ничего не получилось.
Что мне помогло, так это Eclipse в Предпочтения -> PyDev -> Интерпретаторы -> Интерпретатор Python , на вкладке Среда я добавил переменную среды PYTHONIOENCODING и указал ее значение как utf-8 .
Это помогло мне ...