I am using an iMac in my home and I connect to my Windows 8 PC at work occasionally through corporate VPN. For some time now from my home, though I can connect to VPN and access Work PC from my Surface Pro (running Windows 8) I was not able to do the same from iMac. It kept complaining machine not found or Access Denied.
It turned out I needed to upgrade the Microsoft Remote Desktop App for Mac OS X. You can download the new version (8.0.5) released by Microsoft on 12th March 2014. Its available in iTunes Store here. This version sports an improved user interface and other benefits. Using this I was able to Remote Desktop to my Windows 8.1 Update PC at work through VPN from my iMac.