Well, I figured out some more info, but not enough to "fix" my problem for good.
So, the situation is as follows: I have DAL assembly that connects to DB using EntityFramework code fist.
Recently we added strong name to our assemblies, including DAL.
Now, when connecting to database, if last migration was on previous version of DAL, I get exceptions like this one: