So, I finally figured it out. On a fresh install, I have to install Samba, edit /etc/samba/smb.conf to include the Workgroup name and also to enable the line:
wins support = yes
After this I allow Samba in the firewall, reboot and then I'm good to go. I'm assuming restarting samba/networking would work as well, but I just like to reboot after changes like that...old habits...
After all of that, I am able to see and access shares on the Windows 7 machine.