Well i have to say that i have the same problem as you and it was a headache, because i did everything in the tutorial and nothing seems to work BUT!!! i wait like an HOUR for this and then it work properly.
So this was my configuration, just as the tutorial in digitalocean here in the "CNAME" section http://bit.ly/1DL7ue3
Enter Name: www
Enter Hostname: @
Hope it helps!!
PD: My droplet has this example name: example.com (or .net if your domain is .net, etc)
I ran into this same issue and after combining a couple of the answers above, your DNS configuration for example.com should be (with CNAME solving the www. issue):
A --> @ --> IP ADDRESS
CNAME --> * --> example.com.
NS --> ns1.digitalocean.com.
NS --> ns2.digitalocean.com.
NS --> ns3.digitalocean.com.