While trying to redeploy the same WebPart ,I was facing this rather silly error. I tried to do the “cleanup” by right clicking the Project and then redeployed same error appeared. Later figured it out by throwing a search in Google
#1 See if the feature that you're trying to add still exists in the "\Program Files\Common Files\Microsoft Shared\web server extensions\12\TEMPLATE\FEATURES" path. Delete it.
#2 Uninstall the particular Assembly from c:\windows\assembly folder too.
#3 Try to deploy it again.