Correct the missing property within the Certificate.
After opening the SSL Relay configuration tool, the drop down menu containing the certificate is blank. The Citrix SSL Relay service cannot find the certificate and therefore does not start.
When following the exact steps with a Baltimore certificate and a certificate from a private authorithy, the SSL Relay configuration tool found the certificate and the Citrix SSL Relay service would start.
When comparing the certificate that worked with the one from Verisign, the VeriSign certificate was missing the following Enhanced Key Usage property:
Server Authentication (18.104.22.168.22.214.171.124.1)
Without this property, the certificate can not be used by Citrix Secure Gateway or the Citrix SSL Relay.