Not really sure about this. During the installation process it should have created a service that auto starts and shuts down but I am not too sure. If you can stop the service manually first then reboot and see if that solves the problem then you know that this is where the issue is.
This error almost always comes from bad data in the tables. It's strange that it seems to only happen when the server starts up (and it doesn't catch it when you actually create the foreign key). The only thing I can think of is that somehow foreign_key_checks is getting turned off before you create it, and then when the server restarts it finds the bad data, and kills the foreign key.
Have you checked the data in there? This article has a good query for checking for bad data (along with a lot of other causes of MySQL foreign key errors). Check out the very first item in the list under "Most Common Reasons for MySQL Foreign Key Errors". MySQL Foreign Key Errors and Errno: 150
When you go to create the foreign key, you can also check to make sure foreign_key_checks is on:
If it's not 1, then it's not checking data before creating the foreign key.