Use Subdomain with Amazon EC2 Public DNS Address?

Why are you not using your own domain name? Most web services based on EC2 do not use the EC2 public DNS, because that public DNS is likely to change.

What you probably want to investigate is using Elastic IP's so as to give your instances stable IP addresses that you can configure DNS against, then attach these Elastic IP's to your EC2 instances.

Here is the AWS documentation on Elastic IP's: http://aws.amazon.com/articles/1346

Of course, if you plan on using a load balanced configuration, then you would actually use Elastic Load Balancer rather than Elastic IP's. In this configuration, your DNS would direct to the ELB.

Here is information on Elastic Load Balancing: http://aws.amazon.com/elasticloadbalancing/

You need to use your own DNS in order to use subdomains. AWS' DNS doesn't have a wildcard record on their dynamically assigned DNS.

You can try:

dig clients.ec2-123-123-123-123.compute-1.amazonaws.com and you will receive 0 answers.

As for:

If I must use my own domain, how can I work around two subdomains? For example, if I create staging.mydomain.com to point to the EC2 instance, now how would I access clienta.staging.mydomain.com?

Again, you need a DNS record clienta.staging.mydomain.com pointing to the IP address of the host and then let Apache or whatever server channel those request to the right vhost. But your clienta.staging.mydomain.com request will never know where to go unless there's an explicit dns entry for it. Some DNS services offer catch-all, wildcard based DNS entries (i.e. *.clients.blah.com), so that could be an option if supported by your DNS provider.

Another suggestion would be to use directories as opposed to subdomains. So, instead of creating a new subdomain, just have clients.domain.com DNS entry, then have clients.domain.com/clienta and clients.domain.com/clientb