Microsoft SharePoint and WebPartTypeId
I figured out that this was because the WebPartTypeId (tp_WebPartTypeId) of the instances in the WebParts table had changed, but where did those ID:s come from and why did they change? Microsoft's schema documentation does not explain this as far as I can see, and I could not find those ID:s anywhere else in the database.
It turned out that the ID, which is stored as a GUID, seems to actually be an MD5 hash of the full name of the assembly and the full name of the type of the web part class. That's why my pages broke - I had changed the version number of the assembly, and the full name includes the version number.
Theoretically, you could get the details of how the WebPartTypeId is calculated by using the excellent .NET Reflector tool by Lutz Roeder, and investigating the WebPartTypeId property of the Microsoft.SharePoint.WebPartPages.WebPart class. Doing so would be naughty of course, unlike in the open source world where you are encouraged to pick things apart and see how they work.
If you know of any documentation that explains how (and more important why) WebPartTypeId is calculated, I'd love to hear about it.