I traced this down, and it looks like there is a series of subtle bugs
that led to this situation.
The bug causing the boot to fail is that gPXE didn't update its
checksum. This was supposed to be fixed in gPXE commit f16668d, but
it looks like gPXE either regressed or the e1000 driver is special in
some way.
The reason SeaBIOS commit a5826b5a exposes this issue, is that commit
a5826b5a broke SeaBIOS' PMM support - the gPXE bug only shows up when
PMM is not available.
So, why did commit a5826b5a break PMM? This appears to be some weird
interaction with gcc and its "-fwhole-program -combine" options. One
of the variables (ZoneTmpHigh) is incorrectly marked by gcc as being
local instead of global after commit a5826b5a. Unfortunately, instead
of getting an error, the build proceeded and had a bogus reference to
the ZoneTmpHigh variable - which caused PMM allocations to fail even
when there was memory.
I've reorganized the build slightly to work around this problem with
"-combine". I've also updated the SeaBIOS linker scripts so that they
will cause a build failure if a similar issue arises in the future.
The latest SeaBIOS git should have this all working again (even with
the current e1000 gPXE).