For me, the sync process gets to "updating server" - it actually
uploads a couple of hundred KBs of data (or so my upload meter says)
then stalls and gives me a "A '400 Bad request' error happened". When I
click on OK, the window closes and FF starts, but obviously the
GoogleSync icon is telling me it's offline.

Funnily enough, it DID sync partially. For example, I installed the
extension on another computer (same software configuration) that runs
the same extensions, and there it worked just fine from the get-go.
It let me store bookmarks etc. via Google Sync on the first try.
It even imported this on the computer where I've been having problems
with the extension.
It also imported the bookmarks from the non-working computer onto the
other one, even though it kept telling me it couldn't sync there.

So I'm still mystified to why this is happening. Seems it's partially
doing the synchronization after all. I also tried just enabling single
sync categories, but all gave me the same error.

More precise error messages could really benefit tracking down errors
like this.