I hate these damn manufacturer specific OEM editions of Windows, they are more pain than they're worth. I spent ages last year trying to recover my neighbours Dell PC, never again. I told them to get vanilla Windows or Linux next time they buy a new system, it's so much easier...
Anyway, just to clarify - the recovery disc that you made how did you make it? is it from a hidden partition on your original hard disk that came with the laptop? i.e. to do a full factory reset on the OS? If it's like the Dell you have to press some awkward combination of keys at a specific moment during boot up to access the factory reset options. Somewhere there should be an option for you to manually choose which partition to use for the boot partition and which to use for the OS*
My recommendation would be to stick with Windows 7 partition and disc formatting tools, don't use any 3rd party stuff or even Linux partition tools (bitter experience tells me that Windows won't play nicely with other partition systems)
How are you partitioning the new disk? iirc you can have a couple of primary partitions + extended (which may contain more partitions within it) or three - four primary partitions. Windows needs at lest one primary partition (for boot) but it might need a primary for the OS as well. I would make no more than two primaries and the rest extended. In theory you can do whatever you like with extended, but I would make no more than two more partitions in the extended area (bitter experience again)
*With vanilla retail versions of Windows 7 I detest all the fixed, default options - I usually install a first copy of Windows to a spare disk, once it's running it doesn't have to registered and additional copies of Windows can be installed exactly where you want them with whatever partitions and drive letters you want to assign. I'm wondering if you can get your Toshiba OEM install media to run from a Windows desktop? You can find vanilla Windows ISO images here:
w7forums Note that the OEM keys you have will not activate the versions on the links above, but you can run them for 30 days without registering, which at least allow you to try the alternative method of installing.