I had the same thing. It's part of packagekit, which has its own update manager. Gnome has it included. In fact, the gnome-core metapackage has it as a dependency. Since I have mintupdate and synaptic installed which work better, this was an annoyance so I uninstalled it. The only trace of it that still exists on my system is libpackagekit-glib2-14 since it is a dependency of gnome-settings-daemon and removing that would get rid of Cinnamon too. Those notifications and the packagekit update manager are gone anyway.
The Mint Update Manager (mintupdate) is a bit smarter when it comes to dependency issues. If upgrading a package causes a dependency conflict, the update won't show up. Other package managers should show the offending package(s). That could be why you don't see any updates there, while packagekit is sending you notifications that there are.
LMDE (tracking Testing) with Cinnamon; Intel Core 2 Duo E8400, Nvidia GeForce GTX 260 (using Nouveau)