Creating a new printer with system-config-printer seems to work. "new printer" "IPP", "generic postscript driver". Print test page. Test page printed.
So it's just the automatic find-the--remote-printer function that's not working.
I have avahi-daemon disabled on both of these computers? Is that the problem? I re-enabled it on both computers and it didn't seem to change anything; it still didn't see the remote printers.