tag cloud not updating with new tags

My tag cloud has stopped updating with new tags. I believe the problem started around the time I upgraded to 2.5.1. I have tried removing and re-adding the tags widget, changing the permalinks structure, deactivating all plugins to see if any of them were interfering with the tag system, and deleting tags and then re-adding them to entries. No luck.

When I add a post to a previously used tag, the count gets updated correctly, but new tags simply do not show up in the tag cloud.