Is your Address Book on your Mac empty? Try the following, add a new test contact on your iPhone. Next try to sync again. If nothing happens, make sure you have set up the Default Contact Sync account on your iPhone to point to Address Book.
To do so, go to Settings>Mail, Contacts, Calendars and under "Contacts" look at what you have set up as "Default"
Well, I used third parties application "Phoneview" to connect to my iPhone 2G where houses all the contacts. Launch the application and click right on Contact Menu -> wait a minute for all contact to show up -> and then select all to highlight contact you want to transfer to Address Book and then hit transfer to Address Book....
Hope that help!