Try doing that random tag method that @jamesroberts posted about earlier. Also contact Shopify asking them to do a resync.
I had done both, dunno which one it was that worked, but all my items gradually resynced across 3 days.
After almost a month without a resolution I decided to try a different app and went for Google Shopping Feed by Adwords Robot. It was quick to setup and after about 30 minutes all 5000+ products are available again in Google Merchant Center. They offer a 14-day free trial and the price is $7 a month thereafter. It'd be nice if Shopify's own feed tool worked, but this seems to be a pretty good alternative.
I should have responded to this thread. I went to the Shopify/Google app, clicked support and asked for a re-sync. They asked why and I sent copies of the emails. They re-synced and within 24 hours I was back on Google. One big caveat. When they re-synced it did wipe out some of my Google Merchant Account settings. I needed to re-do my taxes and my shipping policy link. Taxes are not necessarily a big deal but not having a shipping policy link can prevent you from surfacing and from appearing in enhanced listings.