Cada vez más creo que el problema debe de ser algo en mi propio Python

De todas formas al final conseguí arreglarlo así:
Código Python:
Ver originalasignaturas = dict( zip(deltas, [str(e.asignatura).decode('utf-8').encode(default_locale) for e in examenes]) )
Después de convertirlo a string lo paso a utf-8, y después lo vuelvo a convertir a bytestring con el charset de mi PC, que lo obtengo así:
Código Python:
Ver originalimport locale
default_locale = locale.getdefaultlocale()[1]
Que en este caso es cp1252, no sé por qué

Muchas gracias por todo, creo que ya se han acabado los problemas en el server-side

Saludos y gracias de nuevo :)