I recently just reimaged my PC due to issues, and after installing Outlook 2013 and Shoretel Communicator, I noticed that my IM presence is no longer showing.
Here are the things that worked for me:
1. Under HKCU\Software\IM Providers, the DefaultIMApp was set to Lync, and I had to change it to Communicator. Try re-launching Outlook and see if it works.
2. If IM presence still does not show, under HKCU\Software\IM Providers\Communicator, check and make sure the UpAndRunning value is set to 2. You may have to toggle from 0 and back to 2.