You did the right thing is going up a needle size. The pattern is calling for 18sts/4" and you’re getting 20sts/4" which is close.
Are you knitting a large enough swatch before you measure? The video that knotknittingknots posted is a good one for gauge. The large swatch lets you avoid counting the edge sts and gives you a more accurate gauge.
I’ve had the same thing happen to me. Changed needles, same gauge, go figure. I suggest going up to a 9 to see what you get. You can keep knitting with the same swatch, just put in several purl sts to mark the change to the larger needle. Let the knitting sit for a short time to relax and then measure again.