Messaging had a problem for me till I unlinked Facebook, then reinstalled and linked again.
Skype does work for video calls, I've used it many times. Even used for a video call from my phone to my Dad's Windows 8 PC. Maybe you need to reinstall?
OK...so, if I uninstall messaging (which also removes mail, calendar, people) unlink FB, reinstall and then link FB, that it should fix connection issues? Wonder why it is happening on all 3 of my Win 8 devices?
And you made a video call with a Windows Live account via Skype? I've yet to see that option...only with another Skype user. I really need video chat with a WLM user.