Why SSH stopped working on my Mac - with solution

I use SSH a lot, and recently it stopped working on one of my Macs here at home. I couldn't figure it out for a long time. The only thing I'd changed was that I got a new Linksys router (a WRTG54, which has WiFi and a switch). Previously I was using a Linksys router that was single port, and no WiFi.

Long story short, it came down to the DNS setting on my Mac. Even since I used SonicWall's, I had set my DNS entry to that of the router, not those of my ISP. This was nice, because then if the ISP changed DNS entries (which I pick up via DHCP), I'd be insulated. Well, apparently with the new Linksys, this somehow messes up SSH. It doesn't seem to bother anything else.

The one other nice change though, is that SSH connections now happen noticeably faster than they used to. Thought I'd pass this along in case it ever happens to anyone else.