Formatering af ny harddisk i HP bærbar

Gammel Samsung harddisk er brændt sammen og en ny helt mage til er installeret.
Det er ikke lykkedes at få PC'en til at melde andet end "Operativsystem ikke fundet".
Jeg er klar over, at disken skal formateres (helst i NTFS, men er efterhånden desparat nok til at acceptere FAT32 eller Linux eller...) og har ændret, så der bootes fra CD-drevet, men ligegyldig hvilken CD, jeg giver den, kommer den nævnte fejlmeddelelse.
Jeg kan ikke få fat i de gamle filer, da harddisken som sagt er brændt helt sammen, jeg har ikke nogen recovery fra HP, så jeg har forsøgt med hhv. en Windows Me installations-CD og et Ubuntu-image, men stdig ingen formateringsmuligheder.