Unified Messaging is all set up (followed several tutorials, the most helpful one being this one: http://blog.schertz.name/2010/11/lync-and-exchange-um-integration
When I first dialed our Auto Attendant, it would ask for me to speak a name or dial an extension. The name always failed so I tried to dial an extension. It attempts but ultimately also fails. I now have it configured to only let you dial an extension and when you attempt that, it says "The call cannot be transferred. Returning to main menu." twice before silence.
Voicemail also won't call my phone to let me record a message, either. When I click "Call the Play on Phone number to play or record a greeting for this call answering rule...", if I accept the default value ("user@domain") it just appears to time out. If I dial my extension, I get "The number cannot be dialed because it does not comply with the policy of your organization".
I've read to disable REFER support for the first problem and to check the "Enable dialing of extensions" (or similar) for the second but neither worked.