Here's how we solve this.

We host our DNS with DNS Made Easy, but you could also run your own DNS servers. (We actually have a pair of EC2 instances that we configured as DNS servers and then shut them down, so we're paying a minimal amount for them, but can spin them up very quickly the next time DME is hit with a DDOS.)

We query the ELB CNAME periodically and check its IP. If the IP changes, we update our corresponding A records with the new IP. It's a small amount of code and a cronjob that runs every 5 minutes.

Elegant? No. Get the job done? Absolutely.