I had a similar problem with my Brother MFC-5890CN printer connected to my home network. It would show its status as Offline. Sometimes it would print after a VERY long delay (20 minutes or longer) but usually I simply got printer errors.
My network consists of WinXP and Win7 Dell laptops both with wireless connections, WinVista HP and Win7 Dell desktops both with wired connections along with a Cisco-Linksys router and the Brother network printer described above.
I tried a few of the simpler solutions given in the forum postings, located a Microsoft FixIt tool for network printer problems, and even tried the built-in troubleshooting tool. Nothing solved my problem.
The problem seems to have begun when I attempted to fix a problem with slow internet access. I took some steps to identify better DNS Servers than the "Obtain DNS server address automatically" default that I was using and entered those DNS Server IP addresses in the TCP/IPv4 settings for the network interface cards for the various computers in the home (both wired and wireless).
My solution was to:
1) Use the default of "Obtain DNS server address automatically" for the network interface card TCP/IPv4 settings
2) Go into the Device Manager and under Imaging, delete all copies of the Brother printer. I happened to have four of them (that could be a contributor to my problem). While deleting those devices, I also uninstalled the printer driver.
3) Remove all copies of the Brother printer and faxes from Devices and Printers
4) Restart the PC
5) Then, reinstall the Brother printer software and follow the instructions to restart the PC.
In summary, I put everything back to the state I had before I began changing the IP addresses of the DNS Servers including a clean installation of the printer software. I don't yet know what was really causing the problem, but everything is working now.
Since creating the previous posting, I have put my earlier DNS server settings back into the router and that had no negative impact on my ability to print over the network. The routers settings I have now are the IP addresses of two good DNS servers and the address of my router on my home network. Everything continues to work just fine.
I suspect that the problem was my entering of DNS server IP addresses for the TCP/IPv4 settings of the network interface adaptor in each individual PC. I know that those settings alone cause a print job to be delayed by about two minutes. Earlier, I had also left out the address of my router from the router DNS server IP addresses, so I suspect that my computer could not locate the printer on my home network. The multiple imaging device entries under Device Manager was likely also causing some trouble since the PC might not know which of the four imaging devices it should use.