Print slow through Print Server when using port 139

We have an unusual problem that just started occurring. An entire department started complaining of really slow printing, to the point the users thought their PC was locking up but actually it was just going very slow!

We use Microsoft 2003 R1 Print Servers for print shares.

We ran protocol analysis and found that when the devices were slow they were communicating over port 139. If we deleted shares and drivers and re-installed on users workstation speed would be normal and when looking at new protocol analysis it showed communications over port 445.

I know port 139 is a NetBIOS port and 445 is SMB or TCP port. My question is how does print decide which port to use and which is the preferred port?

Any pointers would be helpful. Thanks