Restore previous apps after upgrade to 4.2?

I have an old iPhone 3G which had iOS 4.0 installed. I had apps such as Starbuck's app running on it without a problem. I just didn't get the latest incompatible updates.

I tried upgrading to iOS 4.2 a few days ago. Before the upgrade process, it backed everything up to iTunes. It performed the upgrade and then asked if I want to set up the phone as a brand new one or restore from a previous backup. I chose the latter option.

After the upgrade was complete, I had a lot of the data on there (e.g. notes, pictures, email account, music, etc.) but all my 3rd party apps were gone. Now when I try to install some apps such as Starbuck's it won't let me even download them.

Is there any way I can get these apps back onto my iPhone? I don't mind downgrading back to 4.0 (if that's even possible).

UPDATE: The phone was not set up to synchronize applications via iTunes. I was thinking that the applications were going to be transferred to the computer as part of the backup process.

There's no way to download previous versions of apps from the App Store. The only way to install previous versions of apps is by having the IPA file. Syncing with iTunes would have backed up the IPA file. It looks like you're out of luck.