Bueno, no se que procesos has realizado, ya que yo lo he probado de la siguiente forma con VNC:
Accesando openSuSe desde un windows OK
Accesando un Windows desde un openSuSe OK
Igual con Mandriva, Centos, Fedora, Linux Mint y Unbuntu/Kubuntu.
Las únicas guías que he seguido, a sido buscando en google y esas guías me han servido.
No te puedo dar los procedimientos que seguí, porque simplemente las leo, ejecuto me funcionan y listo.
El FreeNX es muy recomendado, pero no lo he probado.
Edito porque olvidé un detalle...
Desde la distribución Linux que use, utilizo el rdp (
Remote Desktop Protocol), para acceder a los equipos windows activando el escritorio remoto o el VNC. Es un programa muy fácil de usar y tiene esa particularidad, acceso por escritorio remoto o vnc.