Sadly, I had this experience lately. Even though I had the firewall explicitly set to allow connections using Screen Sharing, for some reason my Mavericks OS X 10.9 server hiccuped and I couldn’t access it via screen sharing.
Here’s how I resolved my dilemma:
Locked out of a Mac because Remote Desktop has suddenly taken a crap on you? Want to remotely enable Screen Sharing (Apple’s fancy name for VNC)? Well, as long as you have SSH active, you can enable Screen Sharing on Mac OS X 10.5 by following these easy instructions.