Over on the macosxhints' forum site, this thread gave me a solution I hadn't considered - switching from LPR via IP to AppleTalk. So I deleted the LPR via IP printer, enabled AppleTalk (which was added in the 10.1 update) on my desktop machine, then selected the now-visible Brother printer and chose the OS 9 Brother HL-1270N PPD file.
Despite an email from Brother Tech Support posted in the thread that the PPD is only OS 9 comptabile, it works flawlessly in OS X. I can now print multiple print jobs without errors, and I don't need to worry about the randomly switching IP numbers any more. I also switched our iBook, and it works great over the Airport, too.
This should also work for any other AppleTalk capable laser printer that is currently set up under LPR via IP.

