I have struggled with this at least three times in the last 6 months. I think there is a bigger issue that bad or missing characters. Here's the way I fixed it:

1. Backup you device
2. Wipe Device
3. Go through set-up wizard (I probably could have skipped this)
4. Restore device
5. Synchronize

This took about 10 minutes and now everything is fine. Since I didn't change anything in my address book, that error was misleading and sent me on a 2 day goose chase.