If you read the article, you will note that the DoJ does not raise the preemption issue in its letter to NC as to why this is a violation under the Civil Rights Act. Why not? The answer, oddly, has to do with the position DoJ has taken on the ability of federal legislaion to preempt restirctions by states on how municipalities govern themselves. This issue is being litigated by the FCC, and DoJ declined to join the FCC in defending the right of the FCC to preempt state legislation prohibiting local governments from offering broadband services.
Small legal world in 10th Amendment land. But it is also an example of how a legal consistency works, rather than being simply results oriented.
UPDATE: The DoJ has filed a lawsuit against NC. It only challenges the "bathroom provision."