First, try uninstalling the Quick Test Professional Add In from the add/remove programs menu in Windows. Then navigate to your QC server and go to the add ins page which can be found by navigating to http://yourserver:8080/qcbin/addins.html then click More HP ALM Add-ins and then click the link for ''QuickTest Professional Add-in'' Go to the bottom of that page and download and install the appropriate version for the version of QTP that you are currently using.

If the above does not fix the issue I would remove all of the Visual C++ redistributables from the machine then run a repair install of QTP to reinstall the versions that QTP/QC uses. Then after doing the repair on QTP try uninstalling and reinstalling the QTP add-in again. Sometimes certain versions of Visual C++ redistributables and conflicts between 64 bit and 32 bit versions of these redistributables can cause QC to go crazy and cause this issue. See below if you need to repair QTP without media.

For QTP v10: http://eyeontesting.com/questions/432/repair-qtp-10-with-out-media
For QTP v11 http://eyeontesting.com/questions/1103/repair-qtp-11-with-out-media

You can find repair instructions for other versions of UFT here:

http://eyeontesting.com/questions/8710/central-post-for-all-command-line-repair-posts.html