Skype shows my contact as offline to me, and me as offline to them when in actuality we are both online, which we verified through email. Because if shows us offline, we are not able to video call.
In the situation you describe there are a few things you can try.
First, make sure each of your own status is online.
Then, toggle your status offline for 5 or 10 seconds, and then back online.
Or signout from Skype, and sign back in.
Try sending a short IM to the contact. Sometimes that will kick online status to its' correct state.
Or, if you're sure the contact is online, right click on the name on your Contacts list and on the menu that comes up, click Call or Video call. Sometimes that too will kick start Online status.
I have the opposite problem. Skype says contacts ARE ONLINE when they are not.
This seems to be a major bug with Skype - I've noticed this issue for several months now. Yes, I'm running the latest version.
I read on a forum last night that it is a problem with Skype servers not synching correctly.
I tried it last week with my partner at home, we could both see eachother as available or available so it worked fine.
Now he's in a different country and we have the problem again, we both show as offline to eachother when we are without a doubt on-line.
So I guess when we tested it at home we were on the same Skype server.
And now we are on different servers and they do not sync properly
I hope this is fixed soon, I am checking out alternative video call apps!