VisualVoicemail on CUCI-Lync is not the same VV that you use on the phone. It uses the IMAP connection to establish the connection from CUCI-Lync. Make sure ou have IMAP enabled in the COS of the user and that the IMAP service is running. What port are you using for the connection? Can you post your cuci-lync registry configuration?
The problem was that the VM I'm using was once part of my lab domain, and I had pushed the registry entries contained in the HKCU\Policies branch of the registry. Those policies take precedence over any defined in the HKCU\Software folder, and my voicemail settings were not even being referenced.