Auch ich hatte das problem "No Multiboot header found" mit dem Kernel aus dem Tutorial "C-Kernel mit GRUB".
Am Ende war ich so verzweifelt, dass ich einfach nur noch den Code 1:1 da raus kopiert habe, aber das Problem bestand weiterhin
Bei mir funktioniert es jetzt, nachdem ich zusätzlich den Parameter -melf_i386 an den Linker übergebe.
Vielleicht hilft das ja dem ein oder anderen