Please, go over the Getting Started doc and make sure that all the package’s assets are being removed from their instance.
There are certain situations where Salesforce will not allow you to uninstall a package because it could interfere with a part of the system that is not being deleted:
You can’t uninstall a package whenever any component in the package is referenced by a component that will not get included in the uninstall. For example:
When an installed folder contains components you added after installation, Salesforce prevents you from uninstalling the package. For example, if the Tuvis Auto-Sync components are still used in the lead/contact/account/opportunity/task/activity layouts.
When an installed package includes any component on a standard object that another component references, Salesforce prevents you from uninstalling the package. This means that you can install a package that includes a custom user field and build a workflow rule that gets triggered when the value of that field is a specific value. Uninstalling the package would prevent your workflow from working.
When you have installed two unrelated packages that each include a custom object and one custom object component references a component in the other, Salesforce prevents you from uninstalling the package. This means that you can install an expense report app that includes a custom user field and create a validation rule on another installed custom object that references that custom user field. However, uninstalling the expense report app prevents the validation rule from working.
When an installed letterhead is used for an email template you added after installation, Salesforce prevents you from uninstalling the package.
You can’t uninstall a package if a field added by the package is being updated by a background job, such as an update to a roll-up summary field. Wait until the background job finishes, and try again.