We're moving across to Amazon EC2 and are using a load balancer, with
the recommendation that we use a CNAME instead of an A record
I sincerely hope that you're not CNAMEing your apex domain. If your DNS host is self respecting, it won't be allowed. If it's a shameful and slimy host, you'll be able to, but you'll lose a piece of your soul (but you're using EC2 anyway, so it appears that concern for your soul is already minimal).
Quoth Amazon:
You can't use a CNAME record to associate your zone apex with your Elastic Load Balancing instance. DNS rules prohibit the creation of a CNAME record at the zone apex (e.g., example.com). For example, if you own the example.com domain name, you can use a CNAME record for the foo.example.com subdomain name, but not for the example.com zone apex.
Moving on...
...since
load balancers may periodically change ip address.
No, load balancers shouldn't periodically change IP addresses. That's kind of their point. They stay the same and act as an abstraction layer between consumers and the content infrastructure. If someone told you that load balancer IP address may periodically change, ask them for clarity.
Amazon ELB is in place, so the goal is to CNAME your domain to the ELB's name. I understand the situation now.
Unfortunately I don't appear to be able to seamlessly make this transition - I have to delete the A record first, and then add the CNAME, which will potentially result in downtime as the new record propagates.
Without some multicast shenanigans and maybe even a dash of BGP wackiness, DNS itself isn't intended to have zero downtime changes. You can, however, minimize the downtime potential by dropping your records' TTL values down to the lowest allowable amount of time. Typically 60 seconds, but if your DNS host doesn't allow it to go that low, then get your pitchforks buffed because that's just awful. Regardless, drop your records to the lowest number possible, but then wait for however long the previous TTL value was. If your previous TTL value was 3600 seconds, then wait an hour after your changed your TTL value down to 60 seconds.
Once you've waited that long, then you can change your A record to a CNAME and you'll have only about 60 seconds of downtime, roughly.
I've done similar switchovers that involved zero downtime, but syncing was performed on the data stores so that during the murky cut-over period any transactions that filtered to the old and new systems were synced with backend magicks. That usually costs more time and effort than is justified unless you're dealing with lots of users and money.
The TTL is already 60 seconds, however the SOA NXDOMAIN TTL is 1800 seconds
...which will only be a problem if your domain has something happen which returns a NXDOMAIN response, which it won't when you change your record from an A to a CNAME.
so removing the existing A record will potentially result in up to 30 minutes down (so far as I can tell)
No because you're not removing, you're changing, and any reasonable DNS host would commit the removal of the A record and addition of the CNAME all in one fell swoop, so you will not be responding with NXDOMAIN to any requests.
If Dyn makes every change to your zone an atomic action that individually commits to the zone file, then yes you could potentially be returning NXDOMAIN responses. Which is an awful thing for Dyn to do, but wouldn't be entirely surprising.
which I don't appear to be able to change with dyn.com
My opinion (which when combined with $5 can get you a cup of coffee at Starbucks): Dyn is an awful DNS host.
