The foriegn key generation is not dependent on the order of the beans being deployed. The system waits until both beans are deployed and then alters the table.
JBossCMP will only alter the table if the fk-constraint is true and if it actually creates the table. It will not alter a table that is already created.
If that doesn't help try adding some print statements to the code (JDBCStartCommand.java)
I found the bugs in JDBCStartCommand and applied a patch to sourceforge.