Оказалось, что не EF, а наш парень из БД изменил тип данных первичного ключа с int на bigint :), но каким-то образом удалил эту таблицу из моего .edmx, а затем обновление модели не привело к каким-либо изменениям в файле метаданных (ошибка EF ???). Даже удаление всего содержимого .edmx и обновление не оказали никакого влияния.
Достаточно разочарован, я удалил всю созданную папку ADO.NET EF Data Model, а затем заново создал ее с нуля. И это решило проблему.
Я думаю, что либо EF должен обновлять файл метаданных при обновлении файла .edmx, либо он должен позволять программисту изменять его.