I had the app "The Weather Channel" and while I was moving the icons around, I lost it. I removed the app, and went back to the App Store to reload it. The icon still doesn't show up anywhere.
Did you actually delete the app and then had to download it again from the App Store using the cloud icon with the down arrow, or did you just hit the Open button in the App Store?