You might try disabling your firewall as a test. As if not configured properly it could be blocking all local traffic not related to the internet. You know the good ol netbios ports. In theory you probably only want to block netbios ports to the internet and not the internal network. Many firewalls don’t report this traffic anyway, but have checkboxes for such traffic.

You also might check the gateway machine as well. Disable the firewall on the machine trying to print and on the gateway and see what happens.