WordPress Taxonomies becoming corrupted

I have a site which started giving some errors with the database, I think possibly some corruption in the taxonomy tables.

The tags and categories have become "disconnected" somehow. They are still there just not linked to the posts and not appearing in the admin even though the admin shows they are there somehow.

I have no idea what the problem is. Could anyone shed some light? Thanks