Tell you what... when I was restoring a backup I had just made, I found out that I had one bad email that was messing stuff up (it was a proposal emailed to me from the Apple Store). When Gmail Backup tried to restore it, it kept telling me there was a network connection error. I moved the email out of the backup folder and then hit restore again, and everything began working again.

So take a look at the email right after the last one backed up... it may be a problem child. HTH!