Took me a bit for figure out that the certificates isn't the problem but the names. Here's the steps, I did:
1. Check your OpenFire server settings and look for the xmpp.domain value. Remember that value.
2. In the clients, flush the certificates folder; I'm running linux so that folder is ~/.purple/certificates/. In hindsight, I think this step can be skipped because I think Empathy or Pidgin overwrites the folder with the most current certificate.
3. Make sure clients don't log in using the ip address. So no accounts in the form of, firstname.lastname@example.org but rather email@example.com. (so if your xmpp.domain is appsvr1 then the username is username@appsvr1).
4. Edit the host file to satisfy the FQDN requirement. Assuming that your OpenFire server is at 10.209.70.19 and the xmpp.domain is appsvr1, the you have a host entry of 10.209.70.19 appsvr1. You basically alias it.
My users now can bother me again.