Unlocked IPhones 5s Gets locked after inserting SIM
If you can visit the check page at https://www.icloud.com/activationlock/ and get a clear status from Apple for your serial / IMEI then the seller is correct that they removed the Activation Lock.

That is but one of the "locks" that can cause you grief. The next lock is carrier lock. Some phones that were sold under contract are locked to a specific cellular carrier's SIM cards. You need to get a card for that carrier (it doesn't need to be active) and insert it and then connect to iTunes or WiFi or cellular (with active data service) to complete that unlock. Depending on your location - you may be able to request an unlock if the original purchaser didn't complete their contract. You may also need the original purchaser to interact with the carrier in some cases to request an unlock of this device.

Lastly are SIM locks - it doesn't seem you have this last issue from the descripton of the error. (My guess is the device is locked to a carrier or an iCloud account per above) Please comment here if you get a screen shot or more details on the exact wording of the error you see on screen or in iTunes when you connect the phone to a computer.