Gateway tech support will usually send you a restore disc for your laptop, sometimes for free or sometimes for $~10. I'd try getting one of those before sending your stuff back again. I can't believe they don't test that stuff before sending it back out.
One other thing I would suggest is pulling your wireless card. The error you posted would indicate that there was some problem with it (broadcom is a large manufacturer of mini-pci wifi cards). Pull it and try booting up again.