iphone in black list

iCloud has nothing to do with whether or not your phone is on a carrier's stolen phone list. If you bought the phone second hand, it's quite possible that it was lost or stolen before it got to you and was reported by its original owner to their carrier. If that's the case, then only the original owner can have it removed.

"Some lady"? Did this lady happen to work for your cellular carrier? Or was she just some random person? Why was she checking this? Where was she checking it? If she didn't work for your cellular carrier, then contact your cellular carrier yourself and find out if the phone is actually on a stolen phone list.

Where did you buy the phone? Did you buy it from Apple or an Authorized Apple Reseller? If you did not, it wasn't actually new.

You'll need to contact the seller and see if they will give you your money back. Neither Apple nor anyone in this user-to-user forum can do anything about this.