Why do I receive Software Update notifications if there are no updates available?

I keep receiving the following notification about new updates:

If I then run the Software Updater, however, I don't receive any of these updates on Ubuntu 16.04.

Does someone have the same problem?

If you run the new 'Ubuntu Software' application (same icon as the old 'Ubuntu Software Centre', i.e. a capital 'A') the you will see the updates. I'm not sure why 'Software Updater' (icon is a circle with arrows) is out of sync but it is. I asked a related question here

The extra and outdated notification messages are a bug. This has been fixed in development and the update will be released for Ubuntu 16.04 soon, probably later this month (June 2016).

It is possible that there is a distro update. Try running sudo apt update && sudo apt dist-upgrade. Dist upgrades are different than the usual software upgrades so ubuntu may have a problem with it. 16.04 is still new and they changed their software store.