Several ideas:
Sync them to G-Mail now, then sync back to the restored phone.
Sync them to MobileMe now, then sync back to the restored phone.
Sync them to Yahoo now, then sync back to the restored phone.
Sync them to Apple's Address Book over USB now, then sync back to the restored phone.
Sync them to Microsoft Outlook over USB now, then sync back to the restored phone.
Sync them to...well...you get the idea. Whatever you have available to you, sync it with the phone now, then restore, then sync the phone with that particular thing again.