Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Well, you could just re-download it on your phone. Also, a sync probably adds it back in too, but that would take longer.

If you purchased the app, it won't charge you again if you re-download.
 
OK... connect the iPhone to iTunes... click on the iPhone on the left hand side... then click on the Applications tab and click on the app that you want restored. Sync and done...
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.