Unlocked IPhones 5s Gets locked after inserting SIM Bought iphone 5s and it's previous owner  removed icloud account on it. 

I created my own icloud account and associated with it.

Everything is ok, but when i insert a sim card, it requres me OLD icloud credentials (one which was used by previous owner). 

If i enter my own credentials it says : "this account could not be used to activate phone". 

If i remove sim, turn phone on, and enter my credentials it works fine.

What could i do ? (rather than contacting old owner who is remote)

I'm not searching for any illegal (ticks or hacks) about bypassing Icloud.
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.