Thanks for the post.
One of my Chinese users did say that it seems the Linode name servers are blocked. Using a Chinese firewall test I can see that linode.com is also not accessible.
My domain is a .com. My registrar (Enom) does have name servers through Akamai. The Enom interface is pretty terrible. I decided to try dnsmadeeasy since they have a free trial, score well in comparisons, have a nice web interface, and have some neat advanced features like directing traffic to a server that is geographically close to the user (though I won't be using fancy stuff for now). I'm ok with the cost of $29/year if it solves my problem.
I did the switch to dnsmadeeasy about 8-9 hours ago and the Chinese firewall test still shows my site is not reachable from China (lookup result: timeout). Maybe China is just slow to update their DNS?
Does anyone have a Linode that doesn't use Linode's name servers? If so, can you try the Chinese firewall test and see if it works? I'm worried China could be blocking all IPs that Linode provides.