iOS 5 makes you lose everything, or so that was the case from when I had my iPhone 4. You should just be able to go into the app store -> updates then go to purchased -> not on this iPhone, and you'll be able to see all of your apps for download. That's what I ended up having to do.
