We had to wrestle with this a lot too. Like Igor mentioned, make sure that the trust relationship is there. Also, I know you're speaking about CEM clients, but what about your normal workstations? The reason I ask is because regardless of CEM, once we flipped the Notification server to HTTPS, there was no failover. It was either 443 or else. We did have to make sure that, regardless of self signed or 3rd party, our workstations trust whoever signed the NS's SSL certificate. Once that was all in line, it just clicked like magic.
Best advise I can give, setup Altiris to use SSL first, just like in the old days. Once that is working, THEN worry about CEM. It helped us a lot to step back and realize that Altiris has had the ability to operate over 443 from day one. That needs to be treated separately.
Good luck!
Feel free to PM with questions
Paul