Ok, I think I got it! I put the phone in fastboot mode, then ran the following (from the Android SDK):
fastboot erase userdata
I then booted into recovery from the fastboot menu, did one more factory erase/reset for good measure, then rebooted the phone normally.