Database can not be initialized - bin-storage upgrade

Database status can not be retrieved, because I am told, upgrade the database first.

How did you end up in this state?
Is this part of a fresh install, or an upgrade? If upgrade, what version was the old code, and what version is the new code?