Symptoms: I've had an AWS account for years, and I went back and created some instances this past week but then I couldn't access them (via SSH: "Operation timed out"). One oddity was that my old instances had no VPC ID, but every new instance had one (and the VPC was created if none existed).
Solution: I found this troubleshooting guide for connecting, and I followed the step on route tables and added a route with a destination of 0.0.0.0/0 and target of igw... (which is auto-filled with my internet gateway ID).
I've never had to do this before. Hopefully I'll remember!