This seems legit.
The old iOS ( <7.0 ) you could wipe ( Reset->Erase All Content and Settings ) the device and completely sever the connection with old owners account. The original owner would not be able to track it using Find My iPhone.
After iOS7.0 the owner can activate lock the device. If you wipe it, the first thing it will do is to ask you the password for the previously attached iCloud account. While all this is going on, the owner can indeed breadcrumb (track) the device.
The best way is to contact sprint and verizon and check the status of the phone. AT&T is quite a bit more difficult to deal with, but I'd still give it a try.
Good luck living in fear that the previous owner jailbroke it and setup a hidden tracking program. Waiting to steal your bank account information (through emails and a little social hacking), your friends' phone numbers, names, addresses, your credit card information via iTunes. Sounds fun.