Походу сервер криво настроен. Apache? Нужно чтобы он не пытался в эту нелепую cp1251 перекодировать всё. Ну либо править на стороне скрипта - делать .decode('cp1251') для данных, которые вы от сервера получаете, если сервер не ваш, как вы уже и делаете. Это переведёт строку в unicode, с которой можно нормально дальше работать.
Короче, сервер врёт, что отдаёт utf-8. По факту он отдаёт вам cp1251. И Python вам об этом сообщил.
