Yahoo IM definitely works on the Storm. I've been using it since day 1. However, there was already an icon for it on my phone when I first bought it (along with icons for other IM apps, like BB Messenger, Google Talk, etc). You didn't already have an existing icon for Yahoo Messenger?
Try checking your Download folder. If you just re-installed it, maybe the icon is there? Also, just to be sure it's installed on your device, check your Application list: BB Options>Advanced Options>Applications