If they can prove that they were first to market with the game and trademark AND that the other company cloned the game and registed the trademark in bad faith

If they can prove that they were first to market with the game and trademark AND that the other company cloned the game and registed the trademark in bad faith then the trademark should be revoked from the new company and assigned to them. This would be the logical solution. (I am sure some people will harp on about "You cannot prove bad faith" but this is what a court of law should be able to determine. You don't create a copy of another game and use their trademark in any other way apart from coincidence which is highly unlikely in this case)