I had the same problem. My sys admin recommended a reboot (as does this thread), but that takes ~30 min on my system so I avoid it if I can.
What worked for me instead was shutting down Outlook (entirely), then shutting down Communicator (Note: you may have to do this from the sys tray; if you just close the main Communicator window, the program will still be running in the background; take a look at Task Manager Processes, just to be sure). Then restart Outlook and, once it is running and connected to Exchange, restart Communicator. (In my case, I continued to get a warning message on the main Communicator window for the first few moments while it was establishing a connection to Exchange, but it eventually disappeared and everything was back to normal.)
If that does not resolve it for you, or for further assistance, refer to this Support page: How to troubleshoot Office Communicator and Office Outlook integration issues