There is an iPhone app called iDriveLite (free version) that allows you to back up your contacts 'in the cloud'. You can then download them to your new iPhone.
When my wife swapped from iPhone 3 to iPhone 4 (different SIM card) she just sync'd her old phone, the sync'd her new phone, and all her contacts and calendars (most important for her) just transferred straight accross. I didn't even need to get involved, so it must have been easy (she has other talents that I appreciate far more than IT 'stuff')