A solução neste caso é a seguinte. Não use pxelinux.0
se você estiver trabalhando com UEFI em vez de BIOS.
Eu reinstalei meu servidor PXE e usei este guia: link no Wiki do Ubuntu. Funciona como um encanto!
Então, se você usa bios, pode usar a maioria dos guias que pode encontrar on-line (é por isso que eu criei), mas se você usar o UEFI, terá que procurar um pouco mais.
(Agradecimentos a Daniel B )