I get that error if I'm out of memory (only 1MB free in internal), clearing data in Skype fixes it. Or sometimes its because the phone is VERY slow in WiFi, there's an added latency of around +800ms on every new connection. But once Skype is connected, it works well for audio calls.
PS - Do not answer an incoming video calls (not supported), makes the whole phone get stuck.
@Daz - I've been very interested in the innards of Android and trying to learn from compiling onwards to try and understand this issue of Skype. Processor usage is very high even on a normal voice call and I feel its cuz of Java and the crappy VM approach. Is it possible that a native app will be faster, can someone run a native app easily, and will it be possible to convert Skype into a native app and add video support for our ARMv6?
Edited by BLu3HaZe, 28 July 2012 - 01:39 PM.