When I purchased a 3gs from someone through Craigslist, we tried to use the reset all settings method of clearing his data. I let it go for more than 5 hours before giving up and restoring as new through iTunes.
You didn't reset your phone, which would be a reset all settings. You erased all content and settings. GLWT. Restore it in DFU mode if you have problems after.