Our existing Exchange 2010 Unified Messaging (UM) has been working nicely with Lync 2010 for quite a while.
I recently installed a new Lync 2013 setup along side Lync 2010. My plan is to phase the new Lync 2013 in over the next few weeks.
Once Lync 2013 was setup and I moved a user to the new pool, Voice Mail stopped working for that user.
To quickly fix, I did the following:
1. Started Exchange Management Console
2. Went to Organization Configuration -> Unified Messaging
3. Added a new UM IP Gateway and specified my Lync Dial Plan.
4. I then called the DID for the person and verified the called rolled over to Voice Mail.