Network printer is very slow

Resently we installed HP4000 printer using IP address on NT server (SP6a applied). It works very strange – when someone tries to print, task is queued, and status shown is “Printing – Online” It can continue for 10 minutes and finally will be printed, but where this delay could come from? Problem is present regardless whether we print from shared printer or from server itself.
I appreciate your help.