Olá zekkerj, respondendo a suas perguntas...
1. Todas as máquinas rodam Ubuntu 12.04, correto?
Apenas o notebook esta com ubuntu 12.04, o computador onde a impressora está instalada está com o 11.10 e as outras maquinas estão com Ubuntu 12.10
2. Você configurou a impressora no CUPS, correto?
Sim, inclusive as outras maquinas da rede acessam a impressora normalmente, o problema ocorre apenas no notebook
3. Você lembra de ter configurado algum Firewall na máquina que tem a impressora instalada?
A maquina onde a impressora está instalada não possui firewall configurado, acredito que o problema esteja no notebook, pois como mencionei, as outras maquinas da rede acessam a impressora normalmente.
Para tirar a prova, fiz um teste.
Desconectei o notebook da rede e abri o assistente de instalação de impressoras do Ubuntu e a mensagem
"FirewallD não está sendo executado. A detecção de impressoras de rede precisa dos serviços mdns, ipp, ipp-client e samba-client habilitados no firewall". continuou a ser exibida.