If you are sure of your legal footing, and you want your game to be recognizable, then be blatant in your name. Be in your face about what you are doing.
"Counter Clone: If you like CS, you'll like my game better because it's cheaper and I added rocket launchers!"
"MineClone. Get it? Great. Then get it 'cause it's only $1!"
etcNot only is this "in your face" open and honest, it tells people exactly what they are going to get from your game. Additionally, you will get press just for being so brazenly obvious. That kind of press can be gold for you, as all it takes is one well placed mention in the NYT to get you a lot of eyeballs on your game.
This approach is like being the Duke Nukem Forever of clones. You're not apologizing for what you are. Hell no, you're proud of it, so say it!
Good luck.