Just reflash device, and Skype will work again. I had also problems (message not delivered etc) but now it works.

Maybe Google Talk is also a good choice, at least video calls works much better.