Umm, I heard this may be caused by a corrupt database. If refreshing metadata fixes it, it sounds more and more like the database wasn’t fully converted on n agent update. From what I hear, a database repair can fix it.
EDIT: Ok, maybe not “corrupt” database, but a need for optimization. I feel a database optimization may help, and won’t hurt.