I noticed while testing it that that particular rule wasn't checked until all the others were satisfied. I think that might be because of something internal to the validation engine but don't really have the time now to figure that out. I will go back at some point and check it and update here because I also want to require Country.
The good news is it does get checked at some point but it would be preferable to have them all show up at once.