Printer sharing - XP and Millennium! (weird)

Hello,

My problem was to be in the "Networking"section, but I soon realized that it it a software problem.
Here's the situation:

I have an old PC that has an OLD important application that only runs on Windows Millennium (yes, unfortunately!).
Anyway, other computers on the network run XP.
I had to connect a printer to one of the XP devices and add it to the Millennium one so that it can print on it, which I did successfully after some trying and installing some "not really common" protocols.

But what happens is this: (
When I print a document on the Millennium PC, I see it being added to the print queue on XP, but nothing happens until I restart the XP computer! After restart, the document is printed automatically.

Isn't this weird? I tried everything I could think of.
Please help.