Figured I'd throw my two cents in as well - If your printer is working just fine on Linux but you might have all sorts of different OS's trying to connect to it to print, the surefire way of making everything work properly is to have it print via postscript.
One way of doing this is (assuming you have cups installed) going to the cups administration (
http://xxx.xxx.xxx.xxx:631/) and navigating to the printer you want to print to. Copy that URL (
http://xxx.xxx.xxx.xxx:631/printers/Brother_MFC) Then go the 'add printer' dialog of your system. Give it the URL that you copied. When it asks for a driver, just give it a generic postscript driver (i.e. in WinXP: Generic -> MS Publisher Imagesetter). It should "just work". There are a couple nice things about doing it this way (i.e. sharing printers across domains, being able to print from remote locations, etc) but make sure you have your security set right.
After that I can't help much, but try the samba manual
http://www.samba.org/samba/docs/man/...-printing.html (though my brief skim didn't turn up anything too useful).