I've had a load of customers who have been struggling to integrate Skype IM / Voice with their Lync online tenants.
Skype is the replacement for MSN messenger and a great replacement it is too. In fact I would go far as to say its the best service for home use. And that includes many fruit based alternatives, just because you can subscribe to have minutes with which to dial up phones and also have an inbound phone number.
What it isn't, is a corporate united communications system. That's where Lync comes in. But don't panic, they can work together. If your tenant is set up, you can speak to (literally or via messages) another Skype user.
The process is simple but can be slightly strange for the Lync user. In Lync, if my Lync tenant is federated to your Lync tenant, I just search for your SIP address and there you are. I can see presence and I can talk to you immediately. We are federated so that should be the case right?
With Skype its a different kettle of fish. You are federated with Skype (you can change this through your tenant settings by turning off external IM communication), but the thing is, as a Lync user I could just start entering SIP addresses and then start to see people on Skype through my Lync client. Which would make my contacts list huge AND be a bit annoying for people who you don't know who you constantly message. So you *can* add a Skype user to your Lync contacts list, but until they accept you as a friend, you won't be able to see their presence. The same is true the other way. The Skype user can add your Lync SIP address but won't see your presence or be able to contact you until you have added them to your contact list.
In essence, it is protecting you from seeing people that you shouldn't see and also people not seeing you without your permissions.
However the problem comes when your tenant is enabled for external federation / PIC and you cannot add anyone from Skype and no one can add you. In this case I would contact support. They would be best placed to sort out your problem.