New piece of information: I reset my etcd database, which removed the _etcd/registry entry, as you said above.
Then I started a cluster using Vagrant, cluster name "cluster3". All CoreOS nodes connected to etcd immediately, with no errors!
Then I started another cluster in Openstack, cluster name "cluster1". It started throwing errors "501: All the given peers are not reachable", which is what I have been having trouble with. Despite the 501 error, I confirmed that the etcd registration URL is accessible from the CoreOS host on Openstack.
To me, this indicates the failure is not on the etcd discovery server. Is this correct? What is etcd on the CoreOS host actually looking for?