The term ‘Update-Database’ is not recognized as the name of a cmdlet

The solution is to close the Package Manager Console, close Visual Studio and then reopen them.

Rebooting also worked most of the time, but not always.