Ok, mi rispondo da solo (avevo cercato molto in Google semza trovare, ma dopo aver postato ho provato a guardare nelle altre cartelle "ancora giuste" e da lì ho capito come fare).
Per chi ne avesse bisogno, ecco come funziona la storia.
Come accade già anche in XP, ogni cartella può contenere un file di testo (nascosto) chiamato desktop.ini, nel quale si possono salvare alcune proprietà "estetiche e non solo" della cartella, come appunto l'icona, ecc.
Da 7 in poi (o forse già in Vista?), esso può contenere anche un Nome di Visualizzazione (ad es. in italiano) da mostrare in Explorer al posto del vero nome (spesso in inglese) della cartella (questo spiega anche perché la mia cartella si era rinominata: il programma per sostituire le icone che avevo usato era pensato per XP e si è riscritto il suo desktop.ini da zero!).
Questo si ottiene mediante il comando LocalizedResourceName, mentre in C:\System32\shell32.dll sono contenuti i vari nomi delle cartelle di default nelle lingue installate.
Per ripristinare ad esempio il nome in italiano della cartella Programmi, basta aggiungere nel file desktop.ini:
(il -21781 va a pescare la giusta stringa di testo nella DLL; altre cartelle necessiteranno di un altro numero, oppure il testo può addirittura essere immesso direttamente tramite LocalizedResourceName=MioNomeAlternativo).
Mistero risolto!