I started getting the same thing a few days ago. I think another app on my phone may have updated and gone rogue, bringing down gmail. Here's why ...
After gmail starting giving me these messages in re-imaged my phone using a nightly cyangenmod build. While I was re-imaging I also installed GApps. The phone came up and Gmail worked fine. It wasn't until the cloud restore of all my apps started happening that Gmail once again started crashing. That's all on a tmo Galaxy S4 SGH-M919.
I also have an S3 SGH-T999L which I just, minutes ago, did a factory reset on back to the tmo supplied ROM. Same story. As soon as my other apps restore Gmail crashes with the same message. So now comes the arduous task of figuring out which is the naughty app. I mean I only have 72 apps on my phone.