I'm not exactly sure how you do this, but could you try pinging the server to see if you can get a connection? Also, if you're using Windows, have you turned off the windows firewall? Lastly, have you turned off your router firewall? Restarting it isn't enough.
Hmm... What's your ping to the server? Is it possible that your connection timed out before it could be established? Try connecting on a different computer? Try making sure you have a valid account number? (To do this you could create a new Windows user account and play from there)