Shoutbox

I guess it's one of these new-fangled 'special' shortcuts (like a Unix hard link, for those that know). Try finding the msnmsgr.exe program, and right-dragging it to where you want the shortcut. The resulting shortcut should allow you to change the icon.