Also, why didn't I have any trouble when I first started bitcoining a couple of months ago?
That is a very good question.
Not an expert in P2P but:
At least one of the 2 participants needs to be able to accept incoming connections (NAT forwarding, Firewall exceptions etc).
If most of the nodes don't open their ports then some of those that do would need to connect to a lot more than the current maximum (about 60? I doubt the client tries to connect to more).
The new version might have changed in a way that you connect to max 8 other nodes on your own and wait for additional 52 connections on the incoming port. Just guessing from a technical point of view.