[Godzuki]

Saludos, a mi me salia el mismo error. Hay que checar dos cosas:
1. que la tabla sea InnoDB.
2. Que los campos que desees relacionar sean indices (ya sea un primario y un indice normal)

Probablemente el tipo de tabla es MyISAM (no soporta relaciones). Debes cambiar las tablas que desees relacionar a InnoDB (si soporta relaciones).

Para hacer eso, en PHPMyAdmin desde el inicio:
1. Debes dar click en: Bases de datos >> "Nombre_DB"
2. Checar que tus tablas sean InnoDB, en la columna "tipo" debe decir "InnoDB"
Si no son InnoDB:
3. Dar click en el boton "estructura" de dicha tabla (icono de hoja blanca con una mano blanca) junto al nombre de la tabla.
4. Dar click en "Operaciones"
5. Eleir en "motor de almacenamiento" la opcion InnoDB.
6.Dar click en "continuar"

Ahora en la lista de tablas debe salir en la columna "tipo" : InnoDB

Despues de eso debe poderse relacionar los campos.

Nota: en caso de que aun no se pueda, es probable que necesites establecer el campo inicial como "llave primaria" y el otro como "indice"