I have not read the Fox article (or not recently, I can't remember). But this issue is rather stale, it was in the news over a year ago. The issue was that some people who had, according to the USCIS, met the requirements to work in the US, but were in the US under visas or programs other than permanent resident alien, had been granted NC notary commissions.
The issues are that the 14th amendment to the US Constitution states "No state shall make or enforce any law which shall abridge the privileges or immunities of citizens of the United States; nor shall any state deprive any person of life, liberty, or property, without due process of law; nor deny to any person within its jurisdiction the equal protection of the laws." This has been interpreted to mean states may not discriminate against those who are aliens in employment matters, as long as the federal government has determined they are allowed to work in the US.
There is an exception; states can bar aliens from being elected state officials, or appointed state officials who exercise broad discretion. In the case of notaries, the US Supreme Court has decided that notaries do not exercise broad discretion; they only exercise clerical and ministerial discretion. In the case that came to the Supreme Court, the court decided that Texas could not require notaries to be citizens. The person who brought the case was a permanent resident alien.
It appears the NC Secretary of State decided that the Supreme Court case also applies to others that the feds have decided can work in the US, not just permanent resident aliens. It's not the least bit unusual for officers of the executive branch of government to decide that a state law has been superseded by a court decision and ignore the state law. Legislatures are notoriously lax about not repealing laws that have been overridden by the courts; such laws languish on the books for decades, if not a century.
Wikipedia has an article about the case.