Hm, I think that Step 4 should read "Right-click on the iPhone icon and select "Restore from Backup" as described here:
and not "Right-click on the iPhone that’s connected and click ‘Backup’". Selecting "Backup" will simply backup the currently existing data on the iPhone (i.e. the empty contacts records) and will not delete or restore the iPhone as suggested.
I'd personally prefer the iCloud method as I really do not trust iTunes and what it coul do to my iPhone.