Zircon toured with Chthonic, who actually blew up to be a pretty huge band, their Takasago Army was my album of the year 2011. But yeah, maybe I should go out and trademark ReMix and be all like "YO YOU GUYS NEED TO CHANGE UR NAME!"
It's just not a cool thing to do. Especially if the other people have been using the name first.
The obvious and ethical solution to these issues is for the people who chose names that are already being used, to pick a new name. It probably won't be easy -- especially with all those business cards you printed up -- but it's the right thing to do, and in the end, you'll get better recognition, and won't have people saying, "Oh, I thought you were a hipster clothing store."
The Prophet of Mephisto was a bitchin' name and it's just begging for you to get in it again!