It is easy,
If you have a cable modem connection, you should never see this error message.
Only most of DSL customers have this problem because you need to get to network settings and set the MTU manually to 1492 instead of the default 1500.
This is a 100% fix for this error message.
I wish the moderator will erase all other solutions on this board because they were all wrong and does not work.
I hope this helps.
I have the same issue as the first guy, so I followed your instructions. I first changed the MTU to 1492, and it signed me in to PSN. When I tried to go to Playstation Store, it stayed on the loading screen for about 2 minutes before I cancelled. I restarted the PS3, but it timed out again and couldn't sign me in.
EDIT: Disregard the last comment. When I renewed my comp's IP address I could get on the store. Thanks for your advice.