Encontré este link "
How to use UTF-8 with Python" y tiene un apartado con el minidom.
En pocas palabras solo maneja "cadenas byte" o cadenas a secas. Si tratas de pasarle una cadena unicode entonces el minidom de python fallara miserablemente. Para evitar eso tienes que pasar la cadena unicode a una "cadena de bytes" y pasarselo al minidom y ademas que el xml tenga la declaración del encoding.
Edito para saber si es una cadena unicode o un cadena a secas puedes usar la función type.
Ejemplo
Código Python:
Ver originalu = u"Unicode string"
s = "byte string"
print type(u)
print type(s)