I upgraded to a 3GS last Friday, and I had similar problems getting my Apps back. I finally figured out how to fix it... Here's my experience:
I hooked up my new iPhone 3GS, restored from backup (backup which I had made from my old 3G) and none of my apps showed up! I only had the standard iPhone apps and some weblinks. So then I noticed if you click on the iPhone in iTunes, there are a bunch of tabs in the main window. One of them is an Applications tab. I clicked on that, and there you find a picture of your iPhone screen(s) on the right, and a list of all your apps on the left. In the list if Apps, there are check boxes for which Apps you want to be synced to your iPhone. For some reason, all of mine were unchecked. So I checked all of the boxes, synced my iPhone again, and then all of the Apps appeared. Note that you can also rearrange the icon screens on this page too.
But that was not the end - I now had all of my Apps on the iPhone, but all of my old App data was still missing. At that point (after all of the Apps were on the iPhone), I did ANOTHER restore from backup (the same old 3G backup I had used he first time). After that, the Apps had been restored to the same state as they were on the 3G - data and all.
Hope this helps!
One more thing - the first thing you should do - even before making the backup of the old iPhone - is to make sure all of the Apps purchased on the iPhone actually show up in iTunes. One way to do this is "File -> Transfer purchases from iPhone". This moves purchases (songs and Apps) from the iPhone to your computer.
I think all of these issues tend to occur for people who use manual sync (which I was doing on my 3G because it was completely out of disk space).