update your skype

It may be that when you installed the previous version of Skype that there was an issue with the Push Notification System at the time resulting in you getting an invalid push registration.

 

Try uninstalling Skype, and then reinstalling from the Marketplace again. After reinstallation, re-run the app, sign-in, and then let it run for a few minutes to sync contacts and messages. At this point, you should be OK again, but please let me know if you continue to have problems.