hello,
i have the same problem (and some more of my friends do have). i posted a new topic, because all mentioned solutions did not work and the help stopped somehow. but this is really a problem.
and ppmotskula, it has something to do with the version you are using!
if i use the latest 2.0-version, everything is working fine... if i use skype 2.5.0.122, the offline-online-hell is staring over again..
for further things, look to my other topic
http://forum.skype.com/viewtopic.php?p=271187
it might be a problem with the routing and firewall thing, but if so many people having the same problem, we should try to find a solution. my firewall is SuSe Firewall2, running on an routing pc connected to the internet.
yours, mike.