Perhaps they could have used "A Fighting Man of Mars" -- I could swear that was the subtitle that went with John Carter somewhere. Anyway, it would be a bit more suggestive.

Incidentally, the movie is coming to Japan (or just arrived?) and has been heavily promoted here.