This is a known issue with RIM. After a lot of searching I found this RIM article that acknowledges the problem and gives a workaround. I applied it and now version 2 of Yahoo Messenger works fine and the icon is there.
Apparently this problem appears when you try to install version 2 without first uninstalling version 1.
Good luck!
Click on the link below to go to the RIM Workaround page:
BlackBerry Search Results