So.. rebooting the server gets KnowledgeSync to recognize the mail server? Hmm.. could be something on that server causing the problem as this is not a known issue with version 8. If you upgrade and move to a new server at the same time then you may miss the opportunity to understand the cause. The scientist in me is curious whether reinstalling version 8 on the current server would repair something. Or, whether some process on the current server is interfering (i.e., security, anti-virus, etc. )? I guess I would need more clues like which email was method being used, state of network, permissions, etc..
This is a good environment to bounce ideas around. Best of luck and please report back if you find it!