"Printer Paused" or "Printer busy...." error. Why do I get these errors?

Have you tried deleting from Print & Fax and re-adding (+)?

You should update to 10.5.5 - there have been major changes since 10.5.2.

OK, please tell us more details - what protocol you selected in Print & Fax Add dailog, what queue name you used, etc.
Is there any chance that either the computer or printer are using DHCP and the IP address changed?

Yes, looks like LPD with queue name lp1 should work.
The printer busy error is usually associated with incomplete setup (missing queue name), so that's why I asked for details. I did a quick review of the manual, and I don't "think" IPP is supported.
At this point, I'd be looking at the print server (router) admin web pages to see if the queue name was changed or go to Brother's web site or Dlink's web site to see if there are any firmware updates.

And I'd look for an opportunity to use a network printer at some other location to test if there's a CUPS problem.

-I forgot to get clarification - is the printer connected by ethernet or by USB to the router?

I'm seeing something very similar.
We have an HPLJ 2500N - connected hardwired to the in-house network - which is all DHCP, assigned from our Netgear router.
The printer works fine from the wired Mac's in the house (Intel Mini & DPG5), but from the MacBook Pro (1st gen), we get this "Printer Paused" syndrome. All Macs are running 10.5.5. The MBP is normally using wifi. We have recently added a Time Capsule to replace an ailing AEBS, but that was after this problem started.
Several times now, I've created a new printer (from the Print & Fax preference pane), and then just drag over all the print jobs from the stuck queue into the new printer, and it seems to work fine for a short while. I have not yet narrowed down something that triggers the problem, as my dear wife is the primary user of the MBP.

When creating a new instance of the printer queue, I see two choices for this printer - Bonjour and "Network Printer (HP IP)" - and I've tried both. In both cases, the print driver selected has been "HP Color LaserJet 2500 v3010.107"

Does "Printer Busy" mean that the MBP cannot connect to the Printer? Or does it connect and get some sort of error back, which is represented by the "Printer Busy" message in the print queue?

It's certainly possible that the printer gets assigned a new IP address via DHCP in between the working and not working modes - but I'd expect that Bonjour would be able to still find the printer's new IP, and I would not expect the printer queue to assume a fixed IP address. But after looking at the results of clicking on the "info" button on the print queue, it might. I'm going to try using the Bonjour printer model again and see if that helps. It has a printer URL without an IP address: "mdns://hp%20color%20LaserJet%202500%20%280001E69EF65C%29. printer.tcp.local."

Bruce-
I suggest you set the printer to have a fixed (static) IP address.
And I suggest you use the IP printer > HP Laserjet protocol. It is usually the most reliable for models that support it (like yours).

When you print wirelessly at work, is it the LPD protocol?
I'm trying to figure out if some file is corrupted.
Have you tried connecting the Brother printer by ethernet? It has ethernet built-in, right? It probably supports a comm protocol other than LPD, so maybe it'll work with one of those.