When using (K)ubuntu 13.04, my network printer worked fine. After upgrading to (K)ubuntu 13.10 today, I can no longer print. I get the error "The printer is not responding."

I've tried to add the printer again, and it is automatically recognised. I can add it, and select it from print dialogue boxes, but I get the same error.

Brother HL-2040, Kubuntu 13.10 (KDE 4.11.2)

==EDIT==

I attempted connecting the printer directly with a USB cable, and this worked fine, so it's not a problem with drivers. (FWIW I'm using the recommended HL-2040 Foomatic/hl1250.) Further, it prints fine over the network from my wife's MacBook.