I hope that you don't mind me sharing my experience with a Toshiba laptop recently with a co-worker's unit.
My co-workers son decided that he wanted to re-install windows. He totally re-formated the hard drive, to find the same issue. I attempted to recover it for him. In my research I found that many Toshiba laptops have a hidden primary partition that holds recovery data and apparently some bios settings as well. After some failed attempts, I suggested that he get a copy of the recovery disk from Toshiba, which he did (note: Toshiba support wants verification that you are a valid owner of the laptop before they will ship a recovery cd for $30 USD). Still the system would not recover from the recovery cd.
It seems that the disk looks for the recovery data (which he deleted from the hard drive in the re-format), so the disk would not proceed with the recovery. Apparently, the disk also will not complete at all unless it sees the hard drive partitioned exactly with the hidden partition size intact.
I know I was in trouble when I posted on a Toshiba support forum and here and received no responses. IT folks at my job site admitted that they had run into the same issues.
My co-worker sent the unit back to Toshiba and they recovered the system for a price.
So, just be prepared to run into some difficulties if you formatted the recovery partition in the process of reinstalling Windows.
So, I suggest doing some research and I hope that you can get a response from Toshiba or any forum posts that works.
_________________________
"I love it when a plan comes together." - Hannibal Smith