Permalinks redirecting randomly

I recently migrated servers and upgraded wordpress and now it is redirecting to random posts.

This link
http://www.greenprophet.com/2010/07/26/25074/solar-energy-iran/

is going here
http://www.greenprophet.com/2008/01/yael-mer-a-skirt-that-can-save-your-life/yael_mer_green-prophet-2/

I was using a custom permalink structure and when this started happening I changed it to one of the suggested ones. It helped partially. But only partially.

Any ideas how to fix this. It’s killing me.