I had one availability zone where I could connect and another where I could not. After a few hours I got so frustrated that I deleted everything in that availability zone.
Building everything back I had to make sure to create EVERYTHING. This included:
CIDR: 10.0.0.0/24
Destination: 0.0.0.0/0
Target: <Internet Gateway from earlier>
CIDR: 10.0.0.0/24
Routing Table: <Routing Table from earlier
It took me a LOT of fumbling to get all of this. I've ordered the steps in the way I think might be most efficient, but you may have to adjust them to get one item available for the next.
I'm not suggesting that you go thermo nuclear as I did. I'm offering all this information so that you can check these associations to ensure yours are appropriate.