Scenario is 2 x 2010 FE and 1 x UM server
After deploying the second Lync FE pool I found that users in new site (pool) couldn’t call voicemail. Checked the Event logs for the Lync Front End where the users in question are homed and found the following error:-

So based on this it seems that UM doesn’t know about the second lync server 
Of course this sent me directly to the Exch\UM server (either will do as long as they have access to the Exchange Management Tools) for confirming, and so I saw the following:-

No Second UM IP Gateway to the second Lync FE Server…

Since the original 1:1 was created by the PS Script exchucutil.ps1, running this script on UM would find the missing pool and add it as a UM IP Gateway as below:

As seen in the image above the “missing” pool was created, albeit without the DialPlan. Running the exchucutil.ps1a second time resolves that (Go figure)
And a final check on the Exch\UM Exchange Management Tools showed that the new Gateway was nos sorted as below:-

Testing the users on the new pool was now successful.
I had simply forgotten to run the util for the second Lync Pool discovery