Software

What OS are you using to send it print jobs? What sort of documents are you printing?

and shared over the LAN? Or connected via Ethernet directly to the LAN?

You mention you're pretty sure it's Ethernet LAN attached?

What make/model of printer?

Do other people printing to the printer have the same problem?

If you print your documents from another workstation, what is the result.

I the printer will release somebody else's job when you try to print yours, then I'd guess there's a shared spooler somewhere in the system.

Now, since this printer has a built-in printer server, make sure the workstations print directly to the printer.

http://windows.microsoft.com/en-us/windows/help/printer-problems-in-windows
Also it might fix your printer issue in step 2.

1 - On the print server if you are using one look in C:\Windows\System32\spool\PRINTERS for any files hanging out here. If so they may be failed jobs - delete them.
2 - On server or desktops of your users (if you are not using a print server you should think of doing that) go to Start > Devices > look for the printer having issues - right-click go to Printer Properties (not properties specifically "Printer Properties") on the Advanced Tab make sure "Start printing immediately" is checked.

See if that makes any difference. The only issue is if you are not using a print server it may be difficult to deploy this configuration for everyone.

I've seen HP printers print horribly slow if PCL 6 is installed, check the driver and change between PCL5 or PCL5v5.2. Our HP printers usually work the best with PCL5(v5.2)