Ditto. I upgraded from a 2G to a 3GS over the weekend and all of my app data, savegames etc. transferred over.
First I docked my 2G and performed a backup in iTunes.
Then I undocked the 2G, docked the 3GS, and did "Restore from Backup" during setup. It took forever -- like almost four hours.
Lastly, I had to sync the 3GS to get the apps themselves to install.
At the end of all this, it was like a copy of my iPhone 2G (except my app icons weren't in the correct order). I started up iShoot and it took me to the middle of the game I was in, right where I left off. All of my documents and PDFs in Air Sharing were right where they were supposed to be. Other apps (like Twitter clients) remembered me, and so on and so forth.
I'm not sure why it didn't work for you, but it is definitely possible.