Por Fin lo he logrado, despues de bajar y ojear un hermoso manual de aproximadamente 1.800 hojitas, he dado con la solución a mi problema
Por ejemplo para crear mi tabla empresas quedaría mas o menos asi:
Cita: CREATE TABLE Empresa(
Id_empresa INT NOT NULL AUTO_INCREMENT ,
Nombre_empresa VARCHAR( 30 ) ,
Id_categoria INT NOT NULL ,
Id_subcat INT NOT NULL ,
Id_pais INT NOT NULL ,
Id_ciudad INT NOT NULL ,
PRIMARY KEY ( Id_empresa ) ,
INDEX ( Id_categoria ) ,
FOREIGN KEY ( Id_categoria ) REFERENCES Categoria( Id_categoria ) ,
INDEX ( Id_subcat ) ,
FOREIGN KEY ( Id_subcat ) REFERENCES SubCategoria( Id_subcat ) ,
INDEX ( Id_pais ) ,
FOREIGN KEY ( Id_pais ) REFERENCES Pais( Id_pais ) ,
INDEX ( Id_ciudad ) ,
FOREIGN KEY ( Id_ciudad ) REFERENCES Ciudad( Id_ciudad )
) TYPE = INNODB
El problema era que yo indexaba todas las claves de una, y luego aplicaba los foreing key de todas juntas.
Era solo un problema de orden de las instrucciones, bueno por fin lo he logrado gracias a todos ustedes.
BrujoNic, muy sabias palabras esa de partir buscando el manual, de verdad no lo quería hacer de puro flojo y lo admito, pero creo que reconocerlo es un gran paso para algún día llegar a ser como ustedes...
De nuevo se los agradezco montones...
Saludos a Todos 
