Same issue here with a European PSP Go, it just stays on the signing-in screen for ages then brings up the "Skype could not connect. You many be behind a firewall [etc]" error.
I tried forwarding ports 80 and 443 on my router, but no luck. Skype for the PC has always worked fine on the same network. No idea how to open an alternative port using the PSP software.