Sim, deveria. Na verdade, existem várias abordagens diferentes, cada uma com suas próprias vantagens e desvantagens:
Minha solução favorita é instalar o VNC nos PCs Windows e Fedora:
Eu gostaria de me conectar remotamente a uma máquina vmware Linux (Fedora) hospedada em uma máquina desktop Windows7.
Meu entendimento é que isso deve funcionar.
Eu nunca usei VMware, mas deveria ter (como o Virtualbox tem) uma opção para configurar a interface de rede.
Eu sempre escolho bridge e eu ssh diretamente na minha caixa linux. Não tem problema.