I have updated my Ubuntu 13.04 to 13.10 which I have believe cause Skype not to working properly.
For example on 13.04 it was working OK, it is still working on Windows 8 (so there is nothing wrong with my internet connection), but I get the following message each time I have try to send a message:
On hover of the sign I get "Message is not sent". This should be the case if I have not got internet connection or if the person to whom I am sending the message has not got. But this is not the case...
I was able to fix the issue using the link @payorivero gave me.
The issue appears to be caused by incorrect Skype installation ( I have downloaded the Skype from its official web site).
The following line fix the problem permanently:
The above code is showing how to install Skype properly on Ubuntu 13.10: