I found the answer in the comments on this post on Scott Guthrie's blog.

http://weblogs.asp.net/scottgu/archive/2010/08/03/using-ef-code-first-with-an-existing-database.aspx

For those who are seeing this exception:

"The model backing the 'Production' context has changed since the database was created. Either manually delete/update the database, or call Database.SetInitializer with an IDatabaseInitializer instance."

Here is what is going on and what to do about it:

When a model is first created, we run a DatabaseInitializer to do things like create the database if it's not there or add seed data. The default DatabaseInitializer tries to compare the database schema needed to use the model with a hash of the schema stored in an EdmMetadata table that is created with a database (when Code First is the one creating the database). Existing databases won’t have the EdmMetadata table and so won’t have the hash…and the implementation today will throw if that table is missing. We'll work on changing this behavior before we ship the fial version since it is the default. Until then, existing databases do not generally need any database initializer so it can be turned off for your context type by calling:

Database.SetInitializer<Production>(null);

In the first scenario where you changed the Code First Model, before you went and modified the database manually, the answer is to open the (Nuget) Package Manager Console and type:

update-database -verbose

Except - because in this case you are removing a column this will report that it's about to delete something, and it won't delete anything without you explicitly saying that's OK. So you type:

update-database -f -verbose

Now this will delete the column you had in your Model. -verbose says to show you the SQL it runs. If you're scared of just letting it delete things and rather inspect the SQL before it runs, use:

update-database -f -script

That will instead dump the SQL out to a script you can look over, and run manually yourself.

In the case where you went on and deleted the column in the database manually, you now have a more complex scenario on your hands; the EdmMetadata table described in the other answer here contains a hash of the entire database that now does not match the database itself. You can run manual SQL to return the DB to the way Entity Framework expects (the way it was before you manually modified it, which brings it back in line with the hash) by inspecting what you had before and what your db currently looks like.

If that's not feasible you are now in the ugliest part of Entity Framework Code First. You need to eliminate the hash table and reverse engineer the db into code files.

The hash table name depends on the version of EF. In older EF4 like you were asking about, it's called EdmMetadata. In newer EF5, it's called __MigrationHistory (under System Tables in your database if you're looking in SQL Server Management Studio). You'll need to wipe it out.

The good news on the second step, reverse engineering the db into code, is that Microsoft has released a tool into beta that will do this for you.

Walk-through of reverse-engineering a db, and EF Power Tools

You can skip many of the first steps there since they're just setting up a DB and adding some nonsense to it so they can demonstrate what you need to do: Reverse Engineer a db.

Update:

It can also be feasible to use a Manual Migration to work around this scenario. Make a backup of the db, then run:

add-migration WhateverYouWantToCallThis

The modifications to the db EF Migrations that need to be run will appear in the generated C# commands. Now it's up to you to tinker with them to both work around the problems with what it's attempting to do (for example attempting to delete columns that have already been deleted), and put into place things it will need going forward (for example adding back a table you still have in your model but you manually deleted in your db).

Once you've added this and run update-database -f, EF Code First will just accept on faith that you've updated the database the way it needs to be, and update its hash based on the end result. If you made the right changes you can now proceed with Migrations as normal. If this still causes errors you can usually copy the commands of the manual migration out somewhere and delete it, Restore the db from your backup, add a manual migration again and try again. Worst case you resort to the reverse engineering step above.