SharePoint 2010 Web part Deployment Error

When I deploy my web part locally everything is fine. The web part is registered as safe, and is completely usable.

When I deploy the wsp to another server the web part comes back with the following error although everything appears to be deployed correctly (and the SafeControls appear within the web.config). :

Web Part Error: A Web Part or Web Form Control on this开发者_Python百科 Page cannot be displayed or imported. The type XXXXX could not be found or it is not registered as safe.

It is almost the exact same issue as this question. The only difference being that when I look at my web.config on the server I am deploying to I DO see the SafeControls.

Any thoughts on things that I could try to fix the issue? Server settings, how I package or deploy, etc.

I was able to solve my issues by manually removing the solution from the GAC. Then I just tried to add the solution again and everything works well.

I had added the web part in question after the initial upload of the solution (sorry about leaving that part out of the description). Before doing this I was trying to retract and delete from the Central Admin then retry the addition. Apparently this didn't actually delete the solution from the GAC.

The site was using the old version of the solution which did indeed not include a SafeControl for the new web part. Once the old version was removed the addition of the new version went without a hitch and all is well.

Thanks to all for their suggestions.