It depends on what version you are running. In Horizon 6, its pretty simple. Add the new certificate to the Personal folder in the Certificates MMC snap-in and change the friendly name to "vdm". you will then change the old certificate's friendly name to something different. After this is done, you just restart the service and it will use the new certificate.
Make sure to import the certificate as a .p12 sertificate.
On the import screen where you enter the private key (password) for the cert, make sure to import "all extended properties" and "Mark the key as exportable".
Once you import the key, change the friendly name to "vdm" for the new cert and clear out the friendly name for the old cert - that friendly name tells View which to use on start up.
Restart View services or reboot.
Are you getting any errors when trying to use the new certificate? Does the certificate icon have a key on it when it is imported into the MMC snap-in?