Check thru the settings on the PC for the network. If SSID (the name of the network) is set to "Don't broadcast" (the more secure option) then it won't show up automatically, you'll have to type it in under Airport > Other.
Other possibilities include that it has MAC address filtering set, so that only devices with particular hardware addresses can connect, or that Airport is not working - check under Apple menu > About This Mac > More Info > Airport to see if the mac side is happy with itself.
The Firewall settings (on the mac) shouldn't alter your ability to connect to the network, only for the network to be able to connect to you.
The wireless network is broadcasted out of the router, right? or directly from the PC? (in which case there might be Windows Firewall issues...