I recommend incrementally switching each user over to the new password hashing method on their next login. At that point, you know their cleartext password, so you can re-hash it with bcrypt and switch them over to bcrypt. This avoids the need for a "flag day" or contacting all your users. In fact, it is invisible to users: your users never need to know you are transitioning to a new password hash algorithm.
In more detail:
Add another field to the database to indicate which kind of hashing algorithm was used to compute the password hash. In other words, there are two fields associated with each user: one for the password hash, and to indicate the hashing algorithm (SHA512Cng or bcrypt). Initially, password hash algorithm for every user is initialized to SHA512Cng.
When a user tries to logs in, look up the password hash algorithm for their account, hash the password they provided using that algorithm, and compare it to the stored hash. If it does not match, the login is rejected. If they do match, the login is accepted.
Additionally, if the login was accepted and if the algorithm in the database is SHA512Cng, then re-hash the password using bcrypt, overwrite the password hash with the new bcrypt hash, and change the algorithm in the database to bcrypt.
This allows you to gradually transition to the new password hash algorithm, as people log into your service.
Optionally, after a few months have passed, if there are any users who haven't logged in (and thus still have their passwords hashed with SHA512Cng), you could reset their password or email them and request them to log in again or something. However, in many cases this may not be necessary.
P.S. Or, you could use Ramhound's elegant solution of simply bcrypting the password hash. Clever!
bcrupt( SHA512CNG( password ) )
.