Actually, it's extremely easy. Which is why there is hardly any documentation on the subject.
1) Open iTunes on your NEW computer.
2) On the top menu, click: Store> Authorize Computer...
3) Put in your iTunes Store Account credentials - the ones you used on your OLD computer (it should be the same iTunes account you used to buy apps on your iPhone).
4) iTunes will now authorize this NEW computer to use the account previously linked only to your OLD computer (I think you can simultaneously authorize up to 5 computers to pair with an iTunes account).
5) Plug in your iPhone and when prompted click "Transfer Purchases." Doing so will transfer your purchases to your NEW computer (including music, podcasts, pictures, apps, contacts, etc).
6) Thereafter, you should have no trouble syncing your iPhone to either computer, or, in your case, exclusively to your NEW computer.
More information:
http://support.apple.com/kb/HT1848?viewlocale=en_US