Its a lot of chaos out there in case of natty and Katya
One reason is mint used getdeb as source which is void .Others are ppa related
Yes its very strange and sad
If nothing works then you have no option then upgrading your OS
It wont change your settings or anything .
A.)Change the /etc/apt/sources.list to
deb http://packages.linuxmint.com/ lisa main upstream import backport
deb http://archive.ubuntu.com/ubuntu/ oneiric main restricted universe multiverse
deb http://archive.ubuntu.com/ubuntu/ oneiric-updates main restricted universe multiverse
deb http://security.ubuntu.com/ubuntu/ oneiric-security main restricted universe multiverse
deb http://archive.canonical.com/ubuntu/ oneiric partner
deb http://packages.medibuntu.org/ oneiric free non-free
E.) reboot .
You will have LinuxMint 12 running