There are alot of threads about this. Long story short, you have to completely delete it and reinstall it through you browser from the blackberry.com website. Should work fine after that.
I know the entire storm forum is a clutter mess, but its like that becuase people are creating threads because they are lazy and not even looking at the posts on the front page.
I'm having the same problem. Yes, I've redownloaded it, and I can get it to appear. But then, when I tether to the Desktop Manager, it says the BlackBerry Apps or Core Apps need to be updated, and it makes the BBM disappear again. No icon on the menu button, nor in the Instant Messenger folder. I find it installed under Option/Apps. Uninstall, reboot, reinstall... and the vicious cycle starts again.
Been with BlackBerry a total of about 4 hours over this. No solution.
So since the update to 5.0 I have been trying to install BBM. Every time I tried, I couldn't find it anywhere even though it showed as "Installed". And in doing so, I figured out how to get it back...
Open App World, then My World. Delete the BBM from here and you will be asked to Reboot, which you will do. Once your device is back up, reinstall it from your browser, not the other App Center OR App World. Reinstall it only from your browser at BlackBerry - BlackBerry Messenger
AppWorld will "Archive" BBM for whatever reason. As howarmat mentioned, its been discussed many times concerning some of the recent 5.0 leaks. Anyway... install using the provided OTA links amd all will be good. Ignore AppWorld, something is not right with it. For me it lists BBM & Facebook as "archived" even though they are installed and working fine >shrug< .
Posted from my CrackBerry at wapforums.crackberry.com