Once you have the .crt file, import it using Certificate Manager. I used mmc and added the Certificates Snap-in, then right-click on the Personal node and click Import. In Visual Studio, Go to Properties, select Signing and select the new Certificate from the Store. The new certificate was accepted and the Publish was successful after that. Once published, my users were upgraded the same as any normal deployment. There wasn't a need to uninstall first. As a side issue, some users now get another link to the application on the start menu after installing a new deployment, but I think this is unrelated to the above.