Tell PF to fix PS3 fragmented packets
The PlayStation appears to perform packet fragmentation while leaving the don't-fragment bit set. Most home routers don't seem to care -- but there are some that catch this strange behavior and not allow it to pass. pf is generally strict about this sort of thing if you have scrubbing enabled (which is always a good idea.)
Here's a workaround to get you gaming again.
scrub from [ps3-ip-address] to any no-df random-id fragment reassemble
The only required flag here is the no-df, which allows a packet through that would normally be dropped. pf recommends also ensuring IP identifier uniqueness, which the random-id flag enables. I also re-assemble the packets before forwarding them upstream, though this is entirely optional.
The nice part about this is that it only fixes up the stuff coming from the PS3 -- you can still have the rest of your scrub rules cleaning up nasty goop coming into your network as normal.
So far, the only game that is still giving me trouble is GTA4. I successfully join a game about 1 in 4 tries. Every other game I've tried has been absolutely fine.