In case you're using the official ejabberd packages on Debian stable: They're affected by a recent CA policy change (e.g., Let's Encrypt), causing ejabberd to reject newly issued certificates and thereby breaking federation with some remote servers. Deploy this update to fix the issue:
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=1128568#23
You may also want to consider enabling mod_s2s_dialback to deal with remote servers that haven't been updated yet.

