CUPS unable to locate printer

Up until this morning our two iMacs (one on 10.5, the other on 10.6) were able to print OK to our Magicolor 2300DL. Not any more. The printer keeps automatically going into pause on both iMacs. Looking in the console log shows 'CUPS unable to locate printer'. Both iMacs and 2300DL have been power-cycled. The printer can be browsed to quite happily which to my mind suggests that it is there on the network. I have removed the printer and re-added it. I have reset the printer system. Then re-added the 2300DL. The printer will happily print a test page from its own panel.

Digging around a little suggested that perhaps Bonjour was not locating the printer. So I ran Bonjour Browser and did not see any print services displayed. Thought I was onto a solution (although why both iMacs should fail seemed strange).

To double-check I fired up my G4 (running 10.5) and that prints quite happily to the 2300DL. So I ran Bonjour Browser and to my surprise got exactly the same listing as I got on my iMac.

So now I am really confused and not sure where to go next. I even power-cycled the router!