Found my problem! It was the VPC Subnet Routing table was configured wrong. These docs helped me:
Specifically the part that said "Check the route table for the subnet."
Troubleshooting Connecting to Instance
I followed your instructions, but I still can't connect to my instance. I double checked that the security group was correct (ports 7473, 7474, 7687, 22,), I tried all sorts of usernames (neo4j, ubuntu, root), i used the PublicDNS and the Public IPv4...