Are your pictures showing old images on categories, but your product pages are showing the current one?
Is the System -> Configuration -> Catalog -> Catalog -> Frontend -> Use Flat Catalog Product and Use Flat Catalog Category turned on? If so, try rerunning the index on Product Flat Data and Category Flat Data.
That setting should be turned on for speed improvements, but you may need to reindex that if you make changes and it’s not showing up.