Initializing Intel(R) Boot Agent GE v1.2.40???? Help please...

Alright..I sent my laptop to Gateway to replace my DC-In connection and when
I got it back I reformatted it (just cause it needed it) and Upon boot up I
get this message "Initializing Intel(R) Boot Agent GE
v1.2.40..................PXE-E05: The Lan Adapters configurationis corrupted
or has not been initialized. The boot agent cannot continue." And when I
try to reformat anyways...it takes forever, and I mean forever to load the
recovery files from the cd. I kinda googled it and I thought maybe it was a
BIOS thing that I should upgrade...but im not to sure how to flash the bios
without an OS installed. Any help with this problem would be great. I have
a Gateway NX860XL. <--if that matters. Thanks a lot.
Kenny