Ciao inc40,
quando crei una chiave esterna in MySQL devi assicurarti che entrambi i campi da collegare abbiano un indice.

Prova così:
CREATE TABLE `tipologia` (
`codice` set('A','B','C','D','E') NOT NULL default '',
`descrizione` varchar(50) default NULL,
PRIMARY KEY (`codice`)
) TYPE=InnoDB;

CREATE TABLE `paziente` (
`codicefiscale` varchar(16) NOT NULL default '',
`nome` varchar(20) NOT NULL default '',
`cognome` varchar(20) NOT NULL default '',
`eta` smallint(1) unsigned default NULL,
`indirizzo` varchar(50) NOT NULL default '',
`telefono` varchar(15) default NULL,
`codicetipologia` set('A','B','C','D','E') NOT NULL default '',
PRIMARY KEY (`codicefiscale`),
KEY `codicetipologia` (`codicetipologia`),
CONSTRAINT `paziente_ibfk_1` FOREIGN KEY (`codicetipologia`) REFERENCES `tipologia` (`codice`) ON DELETE CASCADE ON UPDATE CASCADE
) TYPE=InnoDB;
ho aggiunto "KEY `codicetipologia` (`codicetipologia`)"