I tried opening Fring (I haven't opened it since they stopped supporting Skype accounts - I switched to Nimbuzz) and didn't get that message. It took a loooooooong time of "testing the connection" but then I did get a login screen. For some reason, it didn't accept my pre-stored user/password, but that's not related to your error.

I have used Fring successfully in the past, but I mainly used it to keep track of Skype and MSN contacts in the same place. It sometimes took a long time for contact lists to show up, but I never did get the specific error message you got.

So my only suggestion would be to try Nimbuzz to see whether you get a similar error message. Maybe a more technical person can explain, but I've found that ability to view the web is handled differently than ability to run other apps in some situations. I've been at a couple of hotels before and decided it wasn't worth it to pay for wireless internet access, but if I was connected to the network, my twitter and/or Skype client would kick in and work just fine. (Like, only certain "ports" are hidden behind the web start page that wants you to pay for access, but some non-browser apps that want access to the internet get it just fine?)

Are you on your home wireless connection, or a work one that might have some strange blocked settings, or a public connection?