Existe um firewall do Windows (ou outro) na sua máquina com o Vista? Você abriu a porta 631 nessa máquina para o IP da máquina Linux? Se não, tente isso. O CUPS usa a porta 631 por padrão para comunicação, portanto você também deve verificar se o seu Firewall na máquina Linux também permite a comunicação da porta 631. Se não estiver na máquina listada, isso também pode causar o problema da impressora não detectável.
Espero que ajude a colocá-lo no caminho certo. É verdadeiramente fácil, uma vez descoberto.