Hmm, I've never tried to use the floppies to launch a branded installation, it does say that it's only for normal installations but I don't see what difference it would make, if I were you I'd give it a go and see.
I'm not sure what type of installation disk your Toshiba recovery disk will be, a normal installation disk can be started from within Windows, where it'll write a boot record on your HD then restart, or you should be able to boot directly from the disk. Have you tried both of these?
If you start the installation from Windows and it doesn't boot into Windows setup, check your boot file (C:\boot.ini) to see if the installation made an entry in there.
If you try and start the installation by booting the CD and it doesn't work, does the BIOS flash any messages up?