Замечено такое-же поведение Skype2.2.0.35/beta на Ubuntu10.04 LTS/amd64, но не так жёстко - 1:10 ... 1:100 рандомно, причём независимо от состояния сети/инета (была версия, что Bind9 (у меня nameserver 127.0.0.1) на компе стартует позже, чем Skype - добавил в скрипт запуска скайпа sleep 10, но ситуация не изменилась).
У кого аналогичные траблы и какие есть идеи, отпишитесь, плииз!