This solution didn't fully help us because we were trying to sync the phone to a new computer, not dealing with a new phone. To be exact, it all worked except app folders.
We have concluded that only the folders that match the category names provided by Apple will be restored. So "Games" will work but "Fun" will not. Furthermore, the content of those folders will only be restored provided that the applications inside those folders match those categories. So if you put an Entertainment app in a Games folder, it will not show up.
As far as rebuilding your folders back manually, we just found a faster way that may be obvious to most of you. When you double click on a folder in iTunes, it will open up on the right side showing you the apps that are in it. Next, sort the apps on the left by name or category, check those you want to add and that's it. Much faster than dragging them around or worse, dragging them around on the phone!
I hope this helps some of you. We certainly spent some frustrating time today moving from Pro to Air. Very un-Apple like, I have to admit!