Ok as stupid as it sounds, today I bought a new Router. And now it works...
Sony screwed up something on their Wi-Fi firmware, so some small amout of routers stopped working properly.
I know how it sounds, but I tried literally everything on my router, nothing ever helped, now I have D-Link router and it works all fine. PSN wasn't the reason I bought a new one, I had other problems with it, but well, it's something to do with Router settings, maybe someone else will be lucky and find out what the problem is.
Sony screwed up something in their coding probably, and there's not too many people with this problem, and so they will probably not going to fix it very soon. :/
Just go to your friends house or some public Wi-Fi network, and you will see that it will work.
For me it is my phone tether that stoped working, I noticed it this morning during my commute. costumer support was of 0 help as expected and I am hoping someone figures something out. work wifi works, home wifi works, tether from tablet works, only my phone one (main thing I use) doesn't work. shows that it is connected to the internet, just fails to sign in.
I'm having the same issue, where ONLY PSN is the issue. I've noticed that if I try 20-30 times, I get lucky once and log in, but even then it is VERY slow. It worked fine before the update. I feel bad for those who, like me, got the new Sly Cooper, and were looking forward to the Cross-save capability. Since you don't have the option to save to the PS3 itself, only upload/download to the cloud, which apparently requires logging in to PSN, I have to be very lucky and/or persistent just to download the save to the Vita or upload it back after playing. Net result, the Vita just doesn't get used for Cross-play, b/c I can't keep it current with the PS3 save without a HUGE hassle.
I tried that, on a public, extremely high bandwidth connection, still doesn't work. I guess there aren't on one of the brands that works, either, if that's the problem. Whoever jacked this up should be demoted. I know it's costing them money on my end, since it's too much of a hassle for me to do impulse buys, which are 90% of my purchases.