Abaixo está uma tradução adaptada de uma resposta feita no StackOverflow (o original) para um problema semelhante ao seu. Pode ver a pergunta original aqui com suas respostas.
Tradução:
Provavelmente você esteja tentando imprimir um texto que contenha caracteres Unicode estrangeiros - em relação ao básico ASCII 128 - que pode ser nosso idioma mesmo. Tente codificar a string Unicode como ASCII 256 primeiro:
unicodeData.encode('ascii', 'ignore')
O 'ignore' vai dizer para pular estes caracteres. Da documentação do Python:
>>> u = unichr(40960) + u'abcd' + unichr(1972)
>>> u.encode('utf-8')
'\xea\x80\x80abcd\xde\xb4'
>>> u.encode('ascii')
Traceback (most recent call last):
File "<stdin>", line 1, in ?
UnicodeEncodeError: 'ascii' codec can't encode character '\ua000' in position 0: ordinal not in range(128)
>>> u.encode('ascii', 'ignore')
'abcd'
>>> u.encode('ascii', 'replace')
'?abcd?'
>>> u.encode('ascii', 'xmlcharrefreplace')
'ꀀabcd޴'
Talvez seja útil ler o artigo "The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!)"*, que acho ser um bom tutorial para o que está acontecendo. Depois de ler, você vai parar de sentir que está só achando o que fazem os comandos (ao menos, é o que ocorreu comigo).
NOTA:
Existe uma tradução do artigo mencionado, como indicado pelo @jsbueno. Tal artigo é de autoria de Joel Spolsky e a tradução é de Paulo André de Andrade. Veja aqui.