Ciao,
ho provato a creare le tabelle con il tuo codice e a creare la relazione a tabelle vuote e non ho avuto problemi. Le tabelle sono già popolate? Se si potrebbe essere che nella tabella utenti ci sia un idregione che non esiste nella tabella regioni e puoi scovarlo con una query del tipo:
SELECT DISTINCT Tab_utenti.Idregione
FROM Tab_utenti LEFT JOIN Tab_regioni ON Tab_utenti.Idregione = Tab_regioni.ID
WHERE Tab_regioni.ID is null
Massimo