Parece que o cliente VNC embutido do OSX faz algo que o Xen não faz. Temos um visualizador VNC chamado 'JollysFastVNC' e funciona muito bem com o Xen. Na verdade, acho que é o único sistema operacional que consegui trabalhar corretamente.
Eu tenho uma conta de hospedagem VPS, e a hospedagem é oferecida pelo Xen, e controlável via VNC. Eu poderia conectar a minha máquina com o meu aplicativo iOS, mas não poderia com o Finder no Mac OS X. Talvez haja um problema desconhecido no cliente VNC do Finder. No entanto, eu preciso de um cliente VNC compatível com Xen para Mac OS X. Por favor, recomende alguns.
Você consegue fazer ping do seu VPS a partir do MacOS? E você pode se conectar ao VNC no VPS com um cliente Windows ou Linux? Isso soa mais como um problema básico de conectividade de rede do que um problema de VPS. Ou o seu servidor VNC não está configurado corretamente.
Se outros dispositivos podem acessar o VNC, você deve tentar outro software. Você já tentou RealVNC? Frango do VNC? Jollys Fast VNC?
Eu gosto muito do Chicken of the VNC. Não consigo imaginar que não funcionaria.