PXE/DHCP using Intel Pro/100 VE

I'm having difficulty getting some Gateway machines with integrated
Pro/100 VEs to boot using PXE. They'll boot fine, fine pxelinux, and
load the kernel, recognizing the ethernet card, but will not make any
attempts (as far as I can determine from the console output) to
autonegotiate DHCP. The kernel then stops, waiting for a root
filesystem. Based on resources I've come up with from this and other
lists' archives, I've tried:

- Building the kernel with menuconfig instead of xconfig.
- Using several different DHCP implementations.
- Removing all expansion cards from the machine.

And lots of other "dumb luck" attempts at things. Does anyone have any
ideas? At present, the DHCP/TFTP/NFS server is Debian (woody).

Thanks in advance,
Marti