A few questions...
1. Did you import the CA-signed certificate and the Root certificate into the ArcGIS for Server Administrator Directory? Those certificates need to match the ones that are set up in your Trusted Certification Root Authority and the one bound to the website in IIS. It can be a pain to import these, depending on whether or not you can generate a PFX file for them to use for import.
2. Are you positive that all certificates in your CA-cert's certification path are trusted on the server in question? Double click the certificate and check out the certification path tab to make sure there aren't any red X's showing up. If there are, that certificate isn't trusted and must be placed into the Trusted Certification Root Authority. This includes the CA-signed server cert, and intermediary certs, and the root cert.
3. Does your CA-signed server certificate (not the root cert, of course) use the fully-qualified (FQN) hostname for the NAME? In other words, does it say GISMACHINE1 or GISMACHINE1.domain.int? The cert must use the FQN; I have not had good luck otherwise.
4. Does your server have a special DNS entry for your network by chance? In other words, is gisserver.domain.int behave as a DNS pointer for GISMACHINE1 on your network? If so, I would recommend that additional SANs be provided as part of the cert. I generally use the host name, any DNS entries, and the server IP as additional SANs besides the FQN as the NAME.