iPhone contact sync no longer working with google
Ugh, of course while typing this, I do the one thing I hadn't tried.

I turned the phone off and then back on again.

It picked the sync up and now I'm back in business.