i've run into that a few times. the partition is missing files. what you were supposed to do (not many people do it) is follow the instructions in the manual and copy your recovery to dvd or cd's. if hp does'nt carry your recovery disc anymore you'll have to obtain a media centre disc and use your license from the halogram sticker on the pc.
i also recommend that you download maxblast from maxtor, create the bootable cd and use the wipe feature. it can also be used to create a backup partion or backup dvd's. great tool and it's legal as well as free.