That is a problem that existed last year as well.

AFAIK, I've been able to avoid it by direct connecting - connect your PS3 directly to your modem, bypassing the router. I also have ports open on my modem, but I don't know how helpful that truly is.

Are both of you guys direct connecting or able to direct connect?