We hit this same issue about a week ago when it seems that Google flipped over all spreadsheets to the "new" format.
This goes for new ones created via the GData api as well. 400 errors everywhere.
I dug into the reports across the GData variant libraries (Python, Java, .Net etc) and eventually found this little nugget: https://stackoverflow.com/a/23438381/1685090
Setting the Etag property to "*" is the answer :)
To be clear, we're setting WorksheetEntry.Etag when we want to run Update() on a worksheet, and we're also setting CellEntry.Etag when doing batch updates via SpreadsheetsService.Batch().
So far it seems to work fine with Google's "new" spreadsheets.
One catch with this approach is that any concurrent/merging operations will be foregone - essentially you are telling Google that your update must blow away any other concurrent prior value in the cells.