This is quite a thorny issue and the law is different in every country and even varies among the States. Copyright is one issue, but likeness rights are another matter altogether (sometimes called personality rights or publicity rights). I remember a case between Paramount Pictures and Leonard Nimoy. A certain brewery was using advertisements that included a likeness of Spock. The Brewery got permission from Paramount, but Paramount never got permission from Nimoy. Paramount owned the intellectual property around Spock, but did not own the likeness of Nimoy.
Genericizing or changing the name doesn't change much. It only helps the product go unnoticed.
A "one off" piece is a different matter, at least in the USA. Artistic expression is protected by the First Amendment, but as soon as you start commercially exploiting a product, that protection is lost. Of course, laws vary by country. And you have to worry not only about the law of the country in which you live, but also the law of the country in which you sell your products. Even the law of the country in which a celebrity lives can some into play.
The decision to go with original characters is the right one, in my personal opinion. I see something wrong with exploiting someone's image without their permission. Plus, you avoid thorny legal issues.