In the example above, I have a two fields (click on image to display whole image).
A choice control containing the options A, B, C and a people picker control beneath it. I created a validation rule on the people picker control that will display a message if the choice is either A or C. The message I display is "You must select a person" which appears at the top when you click on the "Save" button. I named the choice control "Choices" and in the rule I selected from the Named controls column. The rule reads as follows:
Choices == 'A' || Choices == 'B'
Which means: If Choices equals A or Choices equals B. The choices for 'A' and 'B' are case sensitive within the rule.
Is it possible for you to save one of your examples that are failing out to a list template (you might want to make a small list just for this purpose) and post it here. I can then load it into my environment to see what might be happening.
To save a list template, go to List Settings, then Save List to Template (.stp) file, which should automatically include the form.