Welcome to the Xbox Support Forums.
it's quite logical that when your Nattype on your Xbox isn't open that you undergo the same things with your PS3.
I don't have a lot of knowledge with the PS3 Networking stuff and I don't even want, but I am able to assist you with the Xbox problem.
Please refer to this thread and follow all steps one by one and let me know it has solved your problem.
If it wasen't usefull, I'm looking forward to your reply.