Also notice the same problem with my store, started today.
Would love if anyone could have a solution to this.
For the record, my domain has been registered for about 2 weeks and its not new.
Hey, found a solution!
So depending on where you got your domain, head to the settings.
Find something in advanced settings probably that says "A Record" and "CNAME Record"
For A Record, make sure it is set to 126.96.36.199
For CNAME Record, make sure it is set to shops.myshopify.com.
by the way, for the CNAME, make sure you even add that period in the end!
Hope this works for u!