I'm no expert, but I believe that the certificate will always have to match exactly the domain that the user has requested. If user enters mail.foo.net in their mail client config, then cert will have to be a cert for 'mail.foo.net'. If user enters mail.bar.net, cert must say mail.bar.net.
As for the cert, I'm guessing you generated it yourself right? You'll need to generate it all over again. During the process you will be prompted for the 'Common Name (hostname, IP or your name) at which point you should enter the actual name of the hostname for your mail server (e.g., mail.mydomain.com). You may find this helpful: