You've checked the System Preferences, on the first line is the Security button? That opens the Security Window where there's a Firewall button?

I have a desktop imac G5 intel core duo, and just installed Leopard. I had to set the button in the Firewall window to "Set access for specific services and applications."

What I see are three applications that "block incoming connections" and one (LimeWire.app) that "Allows incoming connections." Limewire works even through my wireless network without detecting a firewall.

Also, have you installed the firmware and other latest Leopard follow-on upgrades that Apple just released for PowerBooks?