Du solltest überprüfen, ob der Multiboot-Header auch wirklich in den ersten 8kB (bin mir nicht ganz sicher, aber auf jeden Fall am Anfang) steht. Du solltest den Object-File, in dem sich der Header befindet, als erste Datei dem Linker übergeben.
Ansonsten kannst du mit dem Tool mbchk das ganze nochmal untersuchen, in der Regel gibt das Recht brauchbare Ausgaben.