Connection to EC2 (t2.micro) Works Temporarily, Then Permanently Timesout

I've set up a very basic Ubuntu 16.04 t2.micro EC2 instance in the ap-southeast-1 region. I am able to connect to it via SSH between the time that the instance is started and just before the status changes to "2/2 checks passed." Afterwards, anytime I try to connect to the instance via SSH, the error message "ssh: connect to host xxx.compute-1.amazonaws.com port 22: Operation timed out" is printed.

If I stop the instance, then start it back up, I am able to temporarily connect to the machine via SSH (as soon as the instance appears as "running"). But once the status changes to "2/2 checks passed," I am no longer able to connect to the machine via SSH. This only happens to any instance I create in the us-east-1 region.

I've checked all the documentation, and every security group inbound setting has port 22 exposed to 0.0.0.0/0, and all VPC gateway/subnet/routes/ACL settings look perfect.

If I set up the same type of instance in any other region, I do not encounter this issue whatsoever.

I found a thread mentioning the same issue, almost verbatim https://forums.aws.amazon.com/thread.jspa?threadID=298751&tstart=25, and staff member who replied to the thread mentions that the cause is an "administrative issue on the account."

Is this a known issue? Could it be an issue with my account? Is the cause mentioned in the thread post the same for my account?