There is a similar question, but I tried changing audio settings.
I'm using Ubuntu 9.04 and sometimes when talking to specific person it just doesn't send messages or receive them. It may even show that person as offline for few seconds (even if she/he is not).
That may not depend on the other side, because it happened on Windows and Ubuntu box.
There is a possibility it's not really limited to Skype and it's more of a wider problem, I'm not sure.