I encountered that problem when I had been trying to add a watcher step to an EMR job. Unfortunately, my first tries ended with a Cluster id '' is not valid message. First, I checked whether the cluster really existed and it was the case. Next I started to dig up and after some time I found the reason.
Apache Airflow uses the connections defined under Admin > Connections section and if you verify the one used for AWS, you will see that the "Extra" field contains the JSON like:
If it's not the region you're using usually, you can simply override this value or, which is maybe a better solution if you manage multiple regions, define one connection per region and use it in your step definition.