I won’t totally dismiss Skype being a factor completely, but software-wise they are completely different and probably has nothing to do with it. Also, I use Skype 7 and have no problem. Also, this problem started showing up immediately after the Messenger changes a few weeks ago, not the Skype 7 release.
If you haven’t already done so and you’re using Messenger 2009, please re-revive using the latest version of Reviver (2.3.5).
Either way, getting [connection logs][1] from both of you would be a great start to troubleshooting. Also you might want to review [this thread][2] from a few days ago. My gut feeling is that there’s a specific software that you might have installed that is causing this issue.
Also, knowing what version of Messenger and Windows you’re using, would be a great help too.
[1]: Making a connection log
[2]: Error 8100030d/80072745 sign in errors