I too feared that repositories was the issue. I had removed all catalogs except the default four and then added couple of catalogs. But am getting the same problem.

PS : I do not get any errors when i run apt-get update

I get application updates from xterminal only. But its when i need to install apps.. For apt-get install we need to use actual package name which at times is a pain ( to find the actual name)

not sure why this started but have a feeling that this all started after i disabled automatic updates ( after reading in one of the threads).. not sure though