I had the same issue (I use iTunes on Windows 7). I Bought a new iPhone 5 and used the Backup / Restore method to move my stuff from the old iPhone 4S to the new one. The process only restored all the Apple apps, plus Contacts, Phone Calls, and Messages. When I tried to backup again - hoping it would restore the rest - it went through a restore process in iTunes (for about 5 minutes) and then I got the message that my iPhone will restart but never did (I had to restart it manually).
What I also noticed was that, when I retried, the Backup seemed to be very quick.
I called Apple Support who said that there is a problem with the Backup process. I would be able to restore my Apps via the Purchased Apps process but I would lose all my user data (such as games progress). I was extremely frustrated because I use my iPhone and iPad as tools, not game devices.
I went to the App Store on the iPhone and started downloading some of the Purchased apps from the what seemed to be the iCloud. To my surprise, all app data was there (eg. WhatsApp chats, and The Vault data). I am not sure how this works because I never deliberatelly setup app backup on the cloud, but I suspect that the "Documents and Data" == "On" setting on Settings --> iCloud does exactly that, and in return does not include this information on the PC backup.
All seems fine now (at least for the apps for which I care and tried). The issue I still have is this uncertainty on what exactly is my iPhone doing and where is my stuff at any point in time.
Probably you didn't transfer your purchased apps to iTunes before you restored the phone. Under normal circumstances you would have gotten a warning message about this. Look under Applications in iTunes, check the iPhone tab and see if your apps are listed there, if not they are not backed up. If you have connected your iTunes software with your iPhone Apple account the apps should sync automatically.
Only way to get them back otherwise is to go to Appstore and download them again. Easiest way is to enter Appstore, go to the Update tab and press Purchases/Not on iPhone. (Using the same Apple-account you won't have to pay for your purchased apps again.)
Best Answer
If they aren't available on the App Store anymore, your phone can't download them from Apple.
If you backed up your phone to iTunes before, you just have to restore the apps from there.