SW Center search finds, allows installation of package that doesn't exist

Binary package hint: software-center

After upgrading from Maverick to Natty I want to use greasemonkey in Firefox, so I:

1) Launch Ubuntu Software Center
2) With the "Get Software" tab selected, I type in "grease". "Greasemonkey extension for Firefox" is returned in the search results
3) Click the "Install" button

After clicking install, the SW center shows a progress bar in the search listing, just above the 'Install' button. It looks like the package is being installed. However, the package does not get installed (confirmed w/ dpkg).

This is really confusing - it's not clear to the user what's happening, or why the package isn't installed (I surmise it does not get installed because the 'Install' button does not get renamed to "Remove" and the green 'checkmark' badge does not get applied to the package). There's no indication of what the user should do next to get the package.

Further investigation shows additional inconsistencies:
* The "More info" button in the search results returns a Not Found message, "There isn't a software package called "Xul-ext-greasemonkey" in your current software sources. This is confusing - why does the package get listed in the search results if it doesn't exist?

* If I search for "greasemonkey" with the "Provided by Ubuntu" line selected rather than "Get software", the "Greasemonkey extension for Firefox" package is not returned in the search results. Indeed, searching for greasemonkey anywhere in SW Center other than the "Get Software" area does not return the "Greasemonkey extension for Firefox" package.

FWIW dpkg reports I used to have the package in question on my disk, presumably from when I was on Maverick:
rc xul-ext-greasemonkey 0.8.20100408.6-2build1 extension that enables customization of webpages with user scripts

ProblemType: Bug
DistroRelease: Ubuntu 11.04
Package: software-center 3.1.25
ProcVersionSignature: Ubuntu 2.6.38-7.39-generic 2.6.38
Uname: Linux 2.6.38-7-generic x86_64
NonfreeKernelModules: nvidia
Architecture: amd64
Date: Tue Apr 5 10:33:48 2011
InstallationMedia: Ubuntu 10.10 "Maverick Meerkat" - Beta amd64 (20100901.1)
ProcEnviron:
 LANGUAGE=en_US:en
 PATH=(custom, user)
 LANG=en_US.UTF-8
 SHELL=/bin/bash
SourcePackage: software-center
UpgradeStatus: Upgraded to natty on 2011-04-04 (1 days ago)