If you have Lync setup with Skype, then you may want to look at changing Messenger to Skype. Its a pretty easy fix. As you can see in my screenshot above, my Add External Contact shows Messenger.

To clean this up, we are going to use PowerShell. PowerShell is your friend in Lync 2013 and Windows Server 2012.
From Lync Managment Console, run Get-CsPublicProvider

You should see something like below.

Identity : Messenger
Name : Messenger
ProxyFqdn : federation.messenger.msn.com
IconUrl : https://images.edge.messenger.live.com/Messenger_16x16.png
NameDecorationDomain : msn.com
VerificationLevel : UseSourceVerification
Enabled : True

Identity : Yahoo
Name : Yahoo
ProxyFqdn : lcsap.msg.yahoo.com
IconUrl : https://sec.yimg.com/i/us/nt/b/purpley.1.0.png
NameDecorationDomain :
VerificationLevel : UseSourceVerification
Enabled : True

Identity : AIM
Name : AIM
ProxyFqdn : sip.oscar.aol.com
IconUrl : https://components.premiumservices.aol.com/images/aim.png
NameDecorationDomain :
VerificationLevel : AlwaysUnverifiable
Enabled : True
Look for the one with ProxyFQDN being federation.messenger.msn.com.

Next remove it. For me the command is Remove-CsPublicProvider -identity Messenger
I have seen others use Remove-CsPublicProvider -identity MSN. It all depends on the identity of the service.

Next you need to add the Skype service back in. The command for that is New-CsPublicProvider -ProxyFQDN federation.messenger.msn.com -VerificationLevel UseSourceVerification -Enabled $true -Identity Skype -IconUrl https://images.edge.messenger.live.com/Messenger_16x16.png

Log out of Lync, give it a minute or two then log back in and you will see the new logo.