2020 Update
It's pretty old question but people are still returning to it I see. In case the above answers did not help you, make sure that you are using same data type for the new column as the id of the other table.
In my case, I was using Laravel and I use "unsigned integer" for all of my ids as there is no point of having negative id LOL.
So for that, the raw SQL query will change like this:
ALTER TABLE `table_name`
ADD `column_name` INTEGER UNSIGNED,
ADD CONSTRAINT constrain_name FOREIGN KEY(column_name) REFERENCES foreign_table_name(id);
I hope it helps