Una delle prime cose che faccio di solito (quando si applica) è l'installazione dei Servizi Windows per UNIX nella macchina con la stampante allegata. Ha risolto la maggior parte dei miei problemi. Infatti OS X di solito "dimentica" o non è in grado di identificare correttamente tramite SMB con la stampante / il computer remoto, anche se hai abilitato il guest o un utente specifico salvato nel tuo portachiavi.
Oltre a questo, prova a navigare manualmente per vedere se hai accesso alla stampante in primo luogo. Se è possibile raggiungerlo manualmente, si ha un problema di rilevabilità (in genere risolto dai passaggi precedenti) o i passaggi indicati in altre risposte.
Per quel che vale, installare questi servizi su macchine XP è molto semplice ed è incluso nel CD di XP.
In realtà non si parla di dove è collegata la stampante (versione di Windows), quindi posso solo indovinare. Se la tua stampante è collegata a Windows 7, darei un'occhiata alle altre risposte prima di impazzire.