Toshiba lied to you. Flat out. Go to the link I gave you above to Toshiba's site. Order the recovery discs for the laptop. Hop on eBay and grab this
http://www.ebay.com/itm/380417337465 It's an actual Toshiba brand drive if that makes you feel better or get a used working hard drive for it on eBay or new of some other brand or capacity. I looked up a C655 and it looks to have come with a 250GB drive. Install the hard drive, boot it from the recovery disc you get from Toshiba. It will NOT care in the least what brand/model/serial number is for the hard drive.
Now - PRE-ACTIVATED OEM
Windows installs ARE tied to a specific brand/model of
computer but NOT to the specific machine, serial number, etc. Manufacturers use a function of the motherboards BIOS to add a bit of code called a SLIC then build a check into the specific OEM install version - this is a customized OEM
Windows install disc. All that checks for is that the motherboard is the correct model and has the correct SLIC. It is not specific to your machine though - someone with the same model of laptop could let you use their recovery disc and it will install perfectly fine on yours. Additionally custom pre-actived OEM installs do not promt for the
Windows
There is the other type of OEM
Windows install disc as well which is un-modified. It is just not pre-activated. When you install from one of those you will be prompted for the key on the sticker on the laptop and you will also be prompted to activate
Windows once it's up and running (which is fine to do).