Solution 1:

I just had the same problem with the same symptoms. Apparently I had a package queued up to install. I needed to reset this by deleting the install-queue file found in the ~/.local/share/gnome-software/ directory. To do this open a terminal window and type this command:

rm ~/.local/share/gnome-software/install-queue

If this doesn't fix your problem, you may have a corrupted configuration file, in which case, I'd simply delete all the files in that directory and let them be rebuilt. That can be done using this command:

rm -r ~/.local/share/gnome-software

Solution 2:

I think the highest-voted answers definitely relevant, but I also want to add that for me, old PPA's were causing issues and slowing down Ubuntu Software, even after I removed them from sources.list using add-apt-repository --remove and checked that they were no longer in sources.list. This was because their .list files were still in /etc/apt/sources.list.d and their keyrings were in /etc/apt/trusted.gpg.d.

To remove the .list files one by one:

ls /etc/apt/sources.list.d
sudo rm -i /etc/apt/sources.list.d/<PPAName>.list
sudo apt-get update

Or, to delete ALL PPA's from the sources.list directory:

cd /etc/apt/sources.list.d && sudo rm -i *list*

To remove keys one by one:

sudo apt-key list
sudo apt-key del <KEY_ID>
sudo apt-get update