So I figured out my Samba network issue this morning. It wasn't the Verizon router; it was my Samba configuration on an ancient Linux box I have.

Way back, when I first got Comcast (or I think @Home even) service, I set up my LAN on 10.55.1.1, because the Cincom VPN at the time used 192.168.1. They changed that, but I left my configuration alone.

Fast forward to the new service, and I decided to just let the router default - but I had long since forgotten about the Samba configuration on the Linux box. This morning I realized that maybe I should look at it, and sure enough - smb.conf had references to 10.55.1 all through it. Fixing that seems to have solved the problem. Now I just need to wait for the Windows machines to slowly realize that the shares are there again :)