Cannot route between subnets in different availability zones in AWS VPC

Question

I have created a VPC on EC2 with 3 subnets.

VPC: 172.16.0.0/16

Subnet A: 172.16.1.0/24 (Zone 1b)

Subnet B: 172.16.3.0/24 (Zone 1a)

Subnet C: 172.16.4.0/24 (Zone 1b)

I can ping A <-> B and A <-> C but I cannot ping (or anything else) from B <-> C.

There are different but identical routing tables and network ACLs for the 3 subnets and a really permissive security group. The local routing tables on all the machines look sensible. There are no iptables rules anywhere.

What is going on?

Answer 1

The machines were all built from an AMI and freshly launched. It turns out that the machines needed a reboot to sort out their network settings.