This is a common Issue that occurs in Skype. The user is not able to see his/her contact online. Let’s see why it happens?
Whenever you add a contact especially from your organisation, it appears in your contact list. Whereas the person you added, for him you would appear under the New tab. At this stage even though you added that person as a contact, he has not added you hence you cannot see whether that person is online or not. In the New tab, when he transfers you to the contact list, you would be able to see that person.