The package list needs to be rebuilt.Also, if you try to run apt-get you get:
This should have been done by the backend automatically.
E: Encountered a section with no Package: header
I am not quite certain why it happens yet, but the following fix works:
sudo rm /var/lib/apt/lists/* -vfWhich I got from Ubuntu forums/
sudo apt-get update