Je vous fais part de mon expérience concernant ce problème courant.
J'ai été confronté à ce message malgré de nombreux formatage consécutifs (suite à un changement de carte mère).
J'ai booté sur le Cd de XP (CD de mise à jour) et demandé une suppression de la partition Windows et j'ai ensuite formaté toujours depuis l'install de XP.
Une fois terminé, dès le premier reboot, j'avais ce sale message : "NTLDR manque, pressez une touche pour démarrer". Mon PC marchait très bien malgré ça, mais ça me gonflait.
 
J'ai donc reformaté toujours avec le même méthode (depuis l'install de XP) et encore le même problème. Je recommence, mais cette fois ci je reformate non plus en NTFS mais en FAT32. Idem, dès le premier reboot une fois l'install terminée.
J'ai essayé de réparer depuis la console de récupération, de taper FIBOOT ET FIXMBR toujours de la console, mais toujours rien de nouveau !!!
Bref, j'ai fait ça 6 ou 7 fois pour terminer en reformatant en NTFS et me disant que je serai contraint de vivre avec de message.
 
Mais ça me gonflait sérieux quand même, alors j'ai décidé de tout recommencer et d'installer une vielle version de Windows (win me) pour voir.
Il a fallu d'abord reformater en fat32 depuis la console de récupération XP (format c: /fs:fat32) et j'ai pu ensuite grace à une disquette de boot win me de derrière les fagots installer win Me (le CD n'est pas bootable).
J'ai ensuite procédé à l'install de XP (Cd de mise à jour je le rapelle) et maintenant tout fonctionne.
 
Voilà, je ne saurais expliquer le pourquoi du comment, mais apparemment installer XP sur une ancienne partition XP, c'est pas la même chose que installer XP sur une partition Win Me (ou 98).  
Bon par contre je suis contraint d'être en fat32 (ME oblige) mais tant pis. Je préfère un PC sans message d'erreur en fat32 qu'un pc avec des erreur en NTFS. D'ailleurs il doit exister des méthode pour convertir une fat32 en NTFS, faut que je me rencarde.
 
Bon courage pour ceux (nombreux) qui luttent avec ce putain de message, vous avez au moins là une méthode qui fonctionne. Il faut juste avoir à à sa disposition, une disquette de boot win 98 ou me (avec prise en charge du CD rom), un CD d'install 98 ou me (vraie install, pas mise à jour) et un Cd d'install XP (mise à jour suffit).

 
Partition Magic le fait très bien...
Sinon merci pour ton astuce  

Il doit rester quelques choses dans le mbr
Low level format, et c'est réglé...
Pas besoin de Me ou 98

sauf quand tu as une autre partition avec tes données perso sur le même disque. Donc le bas niveau spa possible dans ce cas.

Pour bien matraquer le MBR, tu démarre avec une disquette de boot de 95, 98 ou ME et au prompt, la commande qui va bien :
 
fdisk /mbr
 
Et voilou : y a plus de MBR (enfin, il est complètement vide).