I had a user report this to me. I was on 10.7.6 and then updated to 10.7.7 and can also replicate the issue. When connected to the Wi-Fi or ethernet connection, i can connect to our RDS hosts. When I swap to my hotspot it sits at initiating connection and then errors with code 0x4.
This is Microsoft Remote Desktop 10.7.7 on macOS.