RESOLUTION:
1. Within the MessageStats console Expand Exchange Organizations
2. Right click on your Exchange Organization name | select properties
3. Select the Connection Server Tab.
4. Depending on what version of Exchange you are running put in a new connection server in and validate it.
Note: Exchange 2003 and 2007 require a mailbox server Exchange 2010 and 2013 require a Client Access Server connection.