For some reason, the advert counts in the categories will sometimes just go totally wrong.
I thought this was due to incorrectly expiring adverts in the default crons, but it just happened again to me.
In the interim until I have time to look for the real problem, I've added a new option in the admin panel which will automatically rebuild the counts every hour.