Probably tried this but....

Remove the catalogues and re-add them, could just be an odd thing...

Which applications in particular are bringing these errors up (I'm aware it could be lots, but name one or two) will be helpful to know.

Has your device had the update?
Have you enabled extras dev or testing and installed anything? - could also have done something to your device.

I remember when i was installing gpodder i had a similar error - so i was told to remove the conflicted apps and re-install. I had installed an app from extras though - not suggesting it will work, but could be heading in that sort of direction if other people can't help?


(P.s. writing in red to get attention is quite annoying)