The strange thing is that Lemmings is an abandonware, so it is legal to make clones of it. But, of course, Lemmings shouldn't be in the title of the clone. That's all!
No?
AFAIK the "abandonware" term is actually non-sense. It's just like those disclaimer you find downloading Mame roms which ask you to delete them after 24 hours if you don't own the dumped PCB.
If the copyright owner still retains it, it's still
illegal to own an abandonware title or a game rom, even if nobody sells it and you can't legally buy it. Sounds a bit stupid, doesn't it? :x
On the other hand, making clones isn't illegal in any way, otherwise we could say MS Word is illegal because it's a clone of the ancient Lotus Abiword.
To avoid any legal issue, I think it should be enough:
1. (of course) not to steal the code,
2. make graphics look different and
3. (as you stated) name the clone completely different.
Anyway, I tried Cheapo and I think it's an amazing piece of software. But first of all I should finish all the levels of the official games...