You don't say where you are or what carrier you use, but it's likely the Craiglist list phone was hacked to unlock it, and when you restored, it was re-locked to whatever carrier/country it was originally locked to.
This is a COMMON problem with phones obtained from craigslist and ebay, which often are stolen ("found") and of unknown origin.
if what modular747 isnt correct then turn your iPhone off take out the sim, put it back in and turn your iPhone back on. it fixed the same problem i had, ive discovered that most carrier issues usually result in me taking out the sim and putting in back in, any other iphone problems and i turn it off and on again.
if you have any other problems then test this out