Try changing your firewall rule to reflect the following:
Protocol: UDP
Direction: Any Directions
Local IPs: Allow any Local IP
Local Address -
Rule applies to all IP addresses of this computer
Specify local ports for this rule: 21, 137-139, 445
Remote Address -
Specify Remote IP addresses for this rule: (IP of your printer)
Specify remote ports for this rule: 21, 137-139, 445
=============================================
You may try allowing both TCP and UDP (if the above does not work) for the protocols. I am trying to allow as little as possible in your case though. CAN you narrow it down to being ONLY the firewall causing this (if you disable the firewall only)?