You would need to add FrostWire to the firewall rules to allow it full permission.

Sometimes, searches are hampered by the ultrapeers you are connected through, so disconnecting, reconnecting 10 mins later might get better results. Just a thought.

One pointer is LW mostly only connects to other LW users, whereas the other gnutella programs connect to many more of the less common ones. I am not sure about FW as I haven't used it in a while.

The firewall icon .. if it was always on when you used LW, then looks mostly like your router/modem at fault. It probably does not utilise UPnP very well, some brands do not have a good UPnP implementation. UPnP is where the program sends a request to the router to open port(s) for it whilst the program is open. When UPnP doesn't work properly, port forwarding the router is way to go.

Not having the firewall icon makes a big difference on performance, although some people say it doesn't bother them. lol

OH .. just a late thought, if you haven't rebooted the computer (or router) since uninstalling LW & installing FW, then the router might be reserving the port for LW ... again probably a upnp issue.