Custom Taxanomy returns -1

After updating to 3.1.2, my custom taxanomies have started to behave oddly.

They seem to “work” as in, displaying them, I can filter through them, view posts they are connected to etc.

But under “Choose from the most used keywords” it returns -1. Same with while typing in a keyword the suggestion comes up as -1.

Any suggestions?
I have just re-installed on a new server and finds the same issue.