В моем случае ошибку выбрасывал urllib.urlencode ((делал поиск по товарам в интернет-магазине), нужно было преобразовать кириллический текст в URL. В общем случае (и в данном конкретном тоже) Python 2 выбрасывает такие ошибки, когда вместо юникода получает нелатинские буквы в формате ascii.
Поэтому нужно преобразовать в юникод:
unicode_str = ascii_str.encode('utf-8')
В моем случае:
raw_params = request.GET.copy()
raw_params[u'q'] = urllib.quote(raw_params.get('q','').encode('utf8'))
где u'q' ...