I would have thought that when all your apps are working on your phone, then a clean install of itunes on a new computer is all you need. When you pair the iphone with the new computer then they should sync together.
I've just gone through a complete new restore with my 3gs iphone at the Apple shop in Birmingham. The technician found a corrupt app that was causing the phone to freeze and not sync with itunes. He suggested when reinstalling apps to do them 3 at a time to esure that there are no corrupt ones. I did this (even though it took forever) and found the corrupt app. All is ok now.