Unable to recover apps after update

I just updated yesterday to iOS5, but when it restored everything at the end of it all none of my apps were restored. When I connect my phone and try to sync them again it keeps telling me they can't be synced because they can't be found (because I lost my backups for them). When I go to the iTunes Store on iTunes to try to re-download them the icon says they're already installed.

I realized that when I go to the app through the App Store on the phone itself, an 'Install' icon appears that'll let me do it, but for apps over 20MB I would need a Wi-Fi connection (since in the iTunes store just shows a greyed out "Installed" icon). Is there a better way to get my apps back without having to buy them all again?

 

It did create copies of my apps, but most of them were deleted. I actually had 5 apps saved and re-installed properly because before I went to iOS5 I downloaded updates for them and new copies were made.

I was hoping there was a better way than using Wi-Fi too. I have quite a few larger apps and there's aren't a lot of free Wi-Fi spots around here, unless I want to camp out in a Starbucks for the next few days. I was wondering if removing them from my list of apps in iTunes would make them downloadable again in the store (ass opposed to the greyed out 'Installed' button), but I'm worried then I'll just have to pay for them again.

----------

Actually, it did back up, but the apps weren't restored anyway. Only my photos and contacts were backed up and restored properly, but nothing else made it. From what I've been reading, it's happened to a few others as well.