A newly developed web part has been deployed to a half dozen site collections. We use one site collection for demo purposes. The new web part is available at all levels of that site collection, and works just fine.
In the main site collection, it is noted as as active web part in the root site of the site collection, but is not available to be deployed. In fact, some web parts that have been uninstalled are listed as available but are not actually there. Even the group heading (under which the new web part was installed) does not appear among those claimed for availability.
In short, the new web part does not appear to be available simply because the web part list does not include it (and has bogus entries). Rebooting the client machine hasn't done anything. Creating a new subsite hasn't changed anything.