Comment 9 for bug 798023

I guess I must have been experiencing a similar problem.

However, I removed all the lists, not just the partial lists, they were rebuild automatically by muon after "check for updates", and no restart needed as mentioned above:

sudo rm -rf /var/lib/apt/lists/partial/*
sudo rm -rf /var/lib/apt/lists/*

Note that the following was of no help whatsoever:
sudo apt-get purge muon
sudo apt-get clean
sudo apt-get install muon