No, the boot order is right. I have several bootable cds/dvds I use frequently.
Turns out my initial thought worked. I extracted the contents of xboxhdm to a new folder and this time copied the contents of isolinux to the root level of the disk, rebuilt the iso and now it's bootable.
So either the isolinux files do have to be in the root OR the original disk just had corrupt files or something like that. Anyhow, the issue is solved by redownloading xboxhdm, extracting, copying xboxhdm/linux/isolinux files to xboxhdm/linux and reburning the .iso
One thing I didn't do was compare the md5sum of the copy on the server with the downloaded copy because the server I downloaded from didn't show the md5 or sha1 hash.