Couple different thoughts. I'm a little confused by how you are using the term "cert with a private key" and what you mean by "use the cert" after you have tried to access it with admin rights. I'm guessing that you are trying to do one of the following:
get a copy of the certificate and do something like verify it, or use it to encrypt something.
get a copy of the certificate and the private key, and use it to do something like sign something.
So... if it's #1, my first bet is that the settings for the certificate have messed up something in the ASP.NET protocols. Verisign would have configured the profile used to generate and sign the certificate in a specific way. This would give the certificate settings that you can't change that might interfere with uploading the certificate. I would check the certificate that gives you problems against the certificates that don't have any problems and see how the extensions on the certificates vary. You can do this through the IE certificate preview pane in the client. Check into any different settings that you find online - there are usually published reports about Microsoft integration issues.
Sadly, if you find a problem, you have to go back to Versign and get a new certificate signed with the correct extensions. If you have a corporate account, ask to talk to their upper tier support, they should be clueful enough to help you find a certificate profile that will work for your tools.
If it's #2 - you may have made the private key for the certificate non-exportable. I'm assuming you're using a software certificate and you uploaded a PKCS12 or other certificate storage file into the browser. At that time, it would have asked if you wanted to be able to export the private key. If you said no (left the box unchecked), then the private key won't leave the browser.
If you have the original certificate/private key storage file around, the answer is painless - delete the cert from your personal certificate store, and reupload it. Be sure to check the exportable box.