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 original- asignaturas = 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 original- import 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 :)