libitguy
...If I "reconfigure and reboot" will it properly shut down everything, and restart it
Yes
(including a Horde mail instance)?
If you mean a user who is logged in to webmail, then No.
That user will have to login again.
It is quite safe to do a reconfigure & reboot, as long as you have NOT made non standard changes to your server eg you have not made changes directly to config files, as these will be lost.
All changes or tweaks should only be done via db commands or custom templates, as those will still be present after a reboot.
Something must have changed in order for that message to appear eg a yum update, or a change made in the admin console "Configure this server menu", or a db command that effected a similar change or the installation of a contrib.
Check the server bash history, ie login as root & press the up arrow or look at bash_history log file for the root or whomever user.
It's even possible you have been hacked if no user really did not change anything.
This is really frustrating since we're moving to a hosted server in a few weeks.
Don't be alarmed, this is probably no big deal. You have just overlooked something that happened, more than likely.