I had the same problem, but managed to make things work (again — all was well until I upgraded to Feisty). Do take the previous poster’s suggestion of making sure that avahi is running first. The only contribution I can make is to describe how I got the firewall to step aside and let Firefly do its work.
First, install Firestarter; it’s available from the “universe” repository in Synaptic. More information on Firestarter is available at http://www.fs-security.com/ . In a nutshell, it’s a GUI for configuring iptables.
In the rest of this post I will recommend setting up firewall rules that allow connections from “anyone” — this is because the machines I am working on are well-protected by another firewall. If you are not similarly protected, or if you are not sure, please be careful! In such a case I would recommend restricting inbound traffic so it is only allowed from machines on your network. Do this by selecting “IP, host, or network” and specifying your network’s IP range in the form 192.168.0.1/24, assuming you’re running a class C network (if all of your machines’ IP addresses start with 192.168 then you’re running a private class C network. Make sure the number after 192.168. matches the one your machines use, then use .1/24 — this should work).
Start Firestarter, and on the “Policy” tab edit the “Inbound traffic policy”. Select the (empty) list under “Allow service” and add two rules: One allowing inbound connections on port 3689 for anyone, and another allowing inbound connections on port 5353 for anyone.
Now edit your (empty) /etc/firestarter/user-pre file (you must su or sudo to do this) so that it contains the following lines:
$IPT -A INPUT -p udp --dport 5353 -d 224.0.0.251 -j ACCEPT
$IPT -A OUTPUT -p udp --dport 5353 -d 224.0.0.251 -j ACCEPT
Save this, then restart firestarter — you might be able to do this from the GUI, but I did it from the command line. Again, you’ll need to su or sudo to do this:
$ /etc/init.d/firestarter restart
You should now be able to see your Firefly share from other machines (iTunes, Roku, Rhythmbox, etc.) — assuming you have properly started Firefly, of course :).
Hope that helps.
–Peter