Have you recently used the proxy server prior to 3.21? It used to work for me until around Oct-Nov. I believe when 3.10 came out, they changed the PSN login handshake.
BTW - if you have a PS3 user that is not associated to the PSN ID, you can browse the PSN store with the proxy bypass (and it gives you the update prompt without the proxy). That's why I think it is a login protocol change.
I am on 2.76 and have the same problem - did you get error 8002A212? I think the problem is that the PSN login handshake changed, so even though we get passed the firmware check, we aren't speaking the same lingo to login. I tried every solution, plus squid and privoxy altering some HTTP headers. Nothing worked. I'm waiting to see if anyone with pre-3.0 is able to get the proxy to work.