Rails migration and the dreaded MyISAM-InnoDB MySql Error

Our team found itself staring at ONE Linux workstation screen trying to fix the following problem:
-- execute("ALTER TABLE widgets ADD CONSTRAINT fk_widgets_gadgets FOREIGN KEY(gadget_id) REFERENCES gadgets(id)")
rake aborted!
Mysql::Error: Can't create table './foo_development/#sql-3779_341.frm' (errno: 150): ALTER TABLE widgets ADD CONSTRAINT fk_widgets_gadgets FOREIGN KEY(gadget_id) REFERENCES gadgets(id)

In my experience this error only means one thing, there are records in the table that violate the foreign key constraint. Finding the orphaned records should be easy right?
select * from widgets where gadget_id not in (select id from gadgets)
0 records found

The worst part about this problem is that it was only happening in only one of the developers sandbox databases as well as in our pre-production environments. It seemed as if it would be impossible to figure out what was happening. Our quest to destroy the ring was just beginning.
I took a look at the constraints table because we had added constraints to the widgets table before, why would this one be any different?
USE information_schema;
SELECT * FROM table_constraints WHERE table_schema = 'foo_development';

The results did not display anything out of the ordinary, the other constraints where there!!! At this point I was running out of ideas. We started to compare the tables in development from test when boom there it was: [gadgets TYPE=MyISAM and widgets TYPE=InnoDB]
SON OF A.... ALTER TABLE gadgets TYPE=InnoDB