Well, after about 12 hours, the books synced, on their own, with no further action from me. I suspect that either the Apple or Audible authorization database was either off line or responding so slowly that it timed out. The response I got from Audible was unhelpful, that I just needed to authorize my account. It was authorized, and I de-authorized and re-authorized, and it made no difference.
I had the same issue tonight and searched for a solution, but came up empty. The logs were not helpful.
After some testing, I decided this was a permissions problem with one of my books, or a part of one of my books. As such, I removed all my Audible files from my iPod and added them back, one at a time.
Eventually, I came to one book that resulted in the, "not authorized," message. The solution was to uncheck it from synching, play it in iTunes on my Mac, then check it to sync.
That resolved the issue. I ejected and plugged in my iPod a few times between books to make sure the issue didn't appear as a result of attaching to iTunes.
Be wary of multi-part books, you may have to play each part (just enough to hear, "This is Audible...") to ensure each part is authorized.
I discovered the same issue, after registering a new iMac and migrating my old user files and music. When syncing my iphone for the first time on the new computer, I got the same error message.
After authorizing the request window that appeared for audible when attempting to play and then playing the audiobook on iTunes, the sync afterwords took place successfully, without the error message. There is a "De-authorize" option available in the pulldown menus for audible, but no "Authorize" choice. Not very clear, but ultimately a simple solution.
Inked, I simplified your solution even more. I have my Audible books on my PC. After installing iTunes I could see all the books but iTunes gave me the same error message when I tried to sync them. I double-clicked each part of each book in turn so it started playing in iTunes (just the first few seconds, "This is Audible. . ."). They started syncing right away to my iPod Nano 7th generation.
I had two two-part books that I just downloaded to this laptop. Despite being asked for my Audible password during the download process, only one part of one of the books would sync through iTunes to my iPod Touch (1st g). I did exactly what Free_Port did and the other three parts synced afterward.