В рамках одной БД все CONSTRAINT'ы должны иметь уникальные имена. Возможно проблема в этом.
Другой вариант -- несовпадение доменов (типа и ограничений) поля внешнего ключа с полем, на которое он ссылается.
Третий вариант -- ссылочные поля должны быть потенциальными ключами.
Четвертый вариант -- родительских таблиц не существует.
Пятый -- подсистема хранения родительских таблиц MyISAM.