In every case that either myself, or my friends, have had with connection problems with PSN or the PS Store it was solved by resetting our routers. It's pretty simple but most people don't do it. Hopefully this helps you out a bit.
Playing: InFamous, Super Robot Taisen OG Saga, Modern Warfare 2