Sync is currently experiencing problems

Update: I now recommend you install Google Chrome and disable the built in Browser as it supports encrypting all synced data.

After picking up a gorgeous Galaxy Nexus yesterday I was running into an issue where my browser data wasn't syncing to the phone. After a little Googling I found this is commonly caused by having all of my synced Chrome data encrypted instead of the default of only encrypting the passwords. These are the steps I went through to get my dat syncing again without losing any of it. The exact error I was getting was "Sync is currently experiencing problems. It will be back shortly."

In Google Chrome open the personal stuff settings page by clicking this link or by opening the wrench menu, and click on "signed in with".  Hit "disconnect your Google Account" to temporarily disable syncing from your browser.

Visit the Google Dashboard and "Stop sync and delete data from Google". I waited until the stored data was removed before continuing so I don't know what will happen if you don't.

Go back to the personal stuff settings page in Google Chrome and sign in with your Google Account to set up sync again. Open the advanced options to make sure "encrypt passwords" is selected and hit OK. You pre-existing browser data is now being synced to the Google cloud.

Open the Accounts & Sync settings page in Android, deselect "Sync Browser" and select it again. Your browser data should now be syncing.