So... just posting this as an answer, to properly close the loop based on the comments under the question:
When setting up a Virtual Machine, you can choose which Cloud Service to place the Virtual Machine in. The Cloud Service is essentially a container which gets assigned a specific IP address, gets a cloudapp.net
name (e.g. myservice.cloudapp.net
), and gets assigned to a region (or affinity group, which is region-specific).
Availability Sets are specific to a given Cloud Service. You may place any of your Cloud Service's VMs in the same Availability Set (or even have multiple Availability Sets, with groups of VMs assigned to specific Availability Sets). However: An Availability Set does not span across Cloud Services.
So: When you went to set up your second Virtual Machine, and you didn't see your Availability Set, that is because you were attempting to deploy to a different Cloud Service.