Sounds like you need the apt database to be put back in sync with itself.

Wade.