Adding new category changes contacts' primary category

I just created a new category in my contact directory and it caused the primary category of all my contacts to change to the new category.

I suppose the steps to repro are:
1. Create category
2. Add some contacts in previous category
3. Create new category
4. Goto a contact's page
5. Note that the primary category == newly created category

I have no idea why this would happen since I would imagine a category has an incrementing id and contacts store that id. Perhaps the contact directory is doing something different.