Skype stopped working for me this week: cannot connect.
I removed account, removed everything from /home/user/.Skype, ran
gconftool --recursive-unset /system/http_proxy
gconftool --recursive-unset /system/proxy
gconftool --recursive-unset /system/osso

No luck so far.

It looks like it cannot find server: I cannot see it connecting e.g. in netstat or Conky. Is there log file to look for DNS attempts or some monitoring app for network access activity?