Quick update.
I created a new VPC with a CIDR of 10.0.0.0/16 and single public subnet with the same CIDR. I then created a three node cluster with a fan network.
This time everything worked. For demos, this could work. It is not likely to work for a production setup since only one availability zone is being used and there are no private subnets.
I will try again some time soon with a more realistic VPC.