Avrdude verification error after months of successful use
Still don't know why, but now have a fix. Re-running the 'Burn bootloader' command from Arduino allowed me to then burn my firmware. Not sure if the issue is with fuses somehow being changed, or what, but this seems to have fixed the issue.

One more fun fact - I tried the same thing on a brand new Mega - same effect. First trying to burn my firmware resulted in a verification error (at a slightly different address), then burned bootloader and re-burned my firmware successfully. Wondering if an update to boards.txt or avrdude came through and changed something.