Managed to fix this by restoring to factory settings and then immediately updating.

Updating by itself did nothing
Restoring to factory settings did nothing

Together they fixed the issue.