It is impossible to say without more information, but it is entirely possible that the internal wiring on one of your speakers is wrong and is out of phase with what it is supposed to be.
But ignoring that as a possibility, as a general rule, there is no harm done to your speakers or amplifier by running one of them out of phase with another one. Usually, it does not sound right, but if the speaker is improperly wired internally, it may be that the receivers are giving you the right answer.
Before tearing anything apart, I would switch the right and left speakers and run the automatic setup again, and see if it says that the same speaker is out of phase with the others, or if the speaker in the right front position seems out of phase (just to be clear, you did say it was the right front that is out of phase with the rest of the speakers?). If the former, I would look inside the speaker (if it is out of warranty) to check the wiring, and if the latter, it may be that you have a strange acoustic problem in your room that makes it seem as though the sound coming from that one spot is out of phase.
By the way, it was smart of you to use a second receiver with an automatic setup to test things. That pretty well rules out it being the receiver that is the problem.
One other point of clarification: You do mean that you switched the wiring going to the one speaker only, correct?