If you're running Red Hat or CenOS, ensure the /etc/sysconfig/network file
has the HOSTNAME field with the FQDN, not just the host name.

HOSTNAME=server1.example.com (good)
HOSTNAME=server1 (bad)

Edit this and reboot the host. Just restarting network services might not
work. Then let us know if the error still continues to be logged.