I think lots of people get this problem, and I was one of them. I just got the game two days ago, and every time I started it up I got the "Failed" message. Elsewhere people have discussed proxies and firewalls and routers and such, but if you're like most people (including myself XD) you're lost when it comes to hardcore computer lingo. Well, after being linked to the help section about proxies, etc. and not understanding a word of it, I scrolled up and found--lo and behold--a section titled "General Troubleshooting," which suggested rooting around in the PSSetup file and clicking random things until something happened. I went into Setup and decided to try switching the game display to Fullscreen Mode, then restarted the client. Presto! The server didn't fail.
I have no idea why this works, but try it.