Ayuda con un servidor de impresión en debian 4.0

Hola lista.

Comento a ustedes un inconveniente que se me ha presentado, agradeciendo de antemano si me pueden dar una luz a mi problema.

Configure un servidor debian 4.0 como servidor de impresión, el cual administra 23 impresoras de red para una carga aproximada de unos 600 usuarios, de los cuales el 85 % son usuarios con maquinas linux (Ubuntu, y PCLinux), el resto son usuarios con maquinas Windows. El problema que tengo es que las maquinas windows no pueden imprimir en él, las linux no presentan problema alguno. Lo curioso es que si realizo un ping desde las windows al servidor de impresiones debian, reciben respuesta al ping pero cuando trato de accederlo para buscar la impresora que le corresponda me envia el siguiente mensaje: "No network provider accepted the given network path".
Alguna idea?

Saludos Cordiales.