Я не вижу в вашем источнике Python следа того, как вы кодируете любые символы, отличные от ascii, которые вы отправляете в запросе. Для URL-адресов (включая строки запроса в них), использующих что-либо, кроме ascii, вам нужно (сделать их юникодом, если они уже нет), затем кодировать их в utf-8 и в процентах экранировать результат (для последнего используйте функцию urllib.quote_plus из стандартного библиотечного модуля Python urllib и, конечно, для кодирования, метод .encode('utf8') строки Unicode - если вам нужно создать строку Unicode из строки байтов с другой кодировкой, используйте строку .decode('latin-1') строки байтов - или, конечно, независимо от названия кодировки, в которой оно находится; -).