Those instructions are for a Firefox update, not a re-installation of your operating system that includes Firefox 29 which has the new version of Sync. The expectation is that there is user data on at least one device that is connected to the older version of Sync.
Since you didn't mention having any other devices connected to your older Sync account, you weren't using Sync as designed (for synchronizing multiple devices) - Mozilla didn't plan on a user having a fresh installation, with their data not being on any Firefox installation, which, IMO, is the main reason Sync was redesigned and upgraded.

Unless you have a backup of your old Firefox Profile (IOW, a backup of your Firefox data), you're going to have to install Firefox 28 and connect to your old Sync account to get your data back from the Sync server, Once you get that done, unlink from Sync and update Firefox to 29.0.1. Then follow the procedure from here Step 3: Create a Firefox account.

Hi there! I'm late to the party but hope this might help you or other future users who may read this.

This workaround is for those who haven't yet upgraded to later than Firefox 28.0, and still have their Firefox profile intact. What you can do is:

1. Backup your history & bookmarks with MozBackup.
2. Upgrade to the latest version of Firefox.
3. Restore Firefox profile with MozBackup.

This way, all your Firefox history and bookmarks are available in the latest Firefox browser. Then simply sign up for the new Firefox Sync account and sync your data again.