The AP reviewed a software package called iPhonebook that aims to make transfering your phonebook to a new phone easy. With Bluetooth, there is no need for iPhonebook, but since only top models include the wireless standard, you may want to take a look. It looks like it works by taking your Outlook address book and sends it to the phone via WAP or BREW.
The software has a monthly fee ($3-$4) since it's meant to be used often so you're always up-to-date.