Una de las primeras cosas que suelo hacer (cuando corresponde) es instalar los Servicios de Windows para UNIX en la máquina con la impresora adjunta. Se ha solucionado la mayoría de mis problemas. De hecho, OS X generalmente se "olvida" o no puede identificarse correctamente a través de SMB con la impresora / computadora remota, incluso cuando tiene un invitado habilitado o un usuario específico guardado en su llavero.
Aparte de eso, intente navegar manualmente para ver si tiene acceso a la impresora en primer lugar. Si puede alcanzarlo manualmente, entonces tiene un problema de capacidad de detección (generalmente resuelto por los pasos anteriores) o los pasos señalados en otras respuestas.
Para lo que vale la pena, la instalación de esos servicios en máquinas XP es muy simple y se incluye con el CD de XP.
Realmente no menciona dónde está conectada la impresora (versión de Windows), así que solo puedo adivinar. Si su impresora está conectada a Windows 7, echaría un vistazo a las otras respuestas antes de enloquecer.