As a note to future people getting this issue:
One possible way to get this kind of error is uploading a sketch that is very close to the size limit. For example, I consistently get it when trying to upload a 5886 byte sketch (official blinklib). In my case, the specific error I get consistently includes:
avrdude: verification error, first mismatch at byte 0x2e00
0x00 != 0x0a
Smaller binaries verify just fine.
In short, the given size limit is inaccurate–try not to get anywhere close to it.