Software app seems to be unaware of package changes from apt-get

Software seems to be out-of-sync with command-line package changes like "apt install, apt remove, apt upgrade, etc.)

This is similar to bug 1583403 but it's a little bit different.

[What happens]
==============
Installing

1. sudo apt install gnome-clocks
2. After installation completes, open the Software app.
3. Search for clocks.
4. The Clocks app shows up with an Install button.
5. Differently from bug 1583403, Clocks does not show up in the Installed page either.
6. Force-kill the gnome-software background processeither by logging out or by running $ pkill gnome-software
7. Open the Software app. Now Clocks show correctly as being installed.

[What should happen]
===================
4-5. The Clocks app shows up with a Remove button in the All page and the Installed page.

Although I'm reporting this bug from Ubuntu GNOME Yakkety, I confirm that this bug also happens on a clean Ubuntu 16.04 LTS install.

Similarly, I'm getting prompts to install system updates that I've installed hours before from the command line. (I can file a separate bug for that although it feels like it might be the same issue.)

ProblemType: Bug
DistroRelease: Ubuntu 16.10
Package: gnome-software 3.20.1+git20160426.1.a976144-ubuntu-xenial-0ubuntu1
ProcVersionSignature: Ubuntu 4.4.0-22.39-generic 4.4.8
Uname: Linux 4.4.0-22-generic x86_64
ApportVersion: 2.20.1-0ubuntu4
Architecture: amd64
CurrentDesktop: GNOME
Date: Tue May 17 21:28:45 2016
EcryptfsInUse: Yes
InstallationDate: Installed on 2016-04-09 (38 days ago)
InstallationMedia: Ubuntu-GNOME 16.04 LTS "Xenial Xerus" - Beta amd64 (20160408)
SourcePackage: gnome-software
UpgradeStatus: No upgrade log present (probably fresh install)