Hmm... are you connecting wirelessly or wired? If wireless the problem may be due to a lack of signal strength or some interference.
There may still be some settings to tweak- maybe try placing the PS3 into the router's DMZ, which would put it outside of any protection given by the router firewall.