Después de darme cabezazos contra la pared descubrí que se ha encontrado un bug que impide conectarse a una impresora de red usando el panel de configuración que viene en Gnome 3.4.
En el propio bug dicen la solución provisional: Usar la herramienta
system-config-printer, que habrá que llamar desde la terminal.
Sigue las instrucciones para conectarte a la impresora de red y todo irá como la seda.