Trovato!!
Il problema è la codifica. Leggendo e facendo ulteriori esperimenti, ho scoperto che
questi file erano in origine nella codifica "windows-1250", ma i vari programmi non se ne accorgono e visualizzano il testo distorto.
Il web è pieno di questi file di testo, a causa del fatto che utf-8 non è usato da molti programmi e gli utenti poverini non lo sanno.

1. Cambiando la codifica il file viene visualizzato correttamente, quindi la sostituzione che facevo non è necessaria. Purtroppo questo risolve il problema solo per me, dato che se il file lo apre qualcun altro e non sa che bisogna cambiare la codifica, vedrà quello scempio

2. ho modificato lo script che adesso non fa altro che leggere il file e salvarlo in uno utf-8 tenendo conto delle codifiche. Ecco il mio script (stavolta senza caratteri unicode):

# -*- coding: utf-8 -*-
import codecs
import tkFileDialog
import sys


reload(sys)
sys.setdefaultencoding( "windows-1250" )

######### Main ########
fileOriginale = tkFileDialog.askopenfile(mode = 'r') #Questo file è in windows-1250

nomeFileAggiustato = fileOriginale.name[0:len(fileOriginale.name)-4] + "_nuovo"+fileOriginale.name[len(fileOriginale.name)-4:]
fileAggiustato = codecs.open(nomeFileAggiustato, 'w', 'utf-8') #Voglio che questo file SIA in UTF-8

for riga in fileOriginale.readlines():
fileAggiustato.write(riga.encode('windows-1250'))

fileOriginale.close()
fileAggiustato.close()

####################