If you synced it, or it auto-synced moments before erasing, could these contacts have been synced to your Mac's address book and now just sync right back to the iPhone? i'd check there, and ChrisF's suggestion about Erase All should do it too. I also just got a used iPhone 4, but it came fully erased, but i did it again anyway for good measure.