it's generally a good idea to give the user more than one way to accomplish the same thing

Agreed. dcosta's idea about changeing the default action would also be a good reason to leave it in there. OK, I see your points on that.

But, what about the option to replace the tracks currently in the queue, without stopping the current track? Does that really sound like a bad idea? Am I the only one that thinks this would be a usefull option?

Maybe this isn't a replacement for "Replace", and is in fact an entirely new option. Or, maybe the current "Replace" should be renamed to "Play"? I don't know.