Apparently in recent versions of Linux, running CUPS 1.4.x (this includes Fedora 13 and Ubuntu 10.10), there's a problem discovering Linux printers. Here's how you fix it...

On your OSX (Leopard or Snow Leopard) system, you can run:

cupsctl BrowseRemoteProtocols=cups

This should immediately solve the problem.

References

Ubuntu Bug Report: CUPS DNS-SD not broadcasting