In this case Toshiba supplied you with a Slipstreamed Install Disc that only supports the Hardware installed in your then New NB. As Toshiba also supply support for any M$ product installed on their computers you need to approach Toshiba for a solution as it's their problem not M$'s.
If you haven't trashed the old Drive Partition you can use M$'s recommendations to install a New M'Board
http://tinyurl.com/j9u7
M$ accepts that replacing the M'Board may be necessary and allows this to occur provided that the CPU hasn't been subject to a Massive Upgrade. So if you have a Pentium CPU it can not be replaced with a Quad Core one and be considered as a Repair it is a Upgrade and should have new M$ Product Installed which the owner pays for.
But as you have replaced the M'Board in this case as a Repair I'm wondering where you sourced the M'Board from, if it was Toshiba which is the expected supplier for replacement things like this for their NB's it should at the very least be the same M'Board and be supported. Toshiba should also support new M'Boards that they supply for their NB's. The install Media can quite rightly be limited to Installed Hardware from New to prevent the theft of M$ Product by others who use it on hardware not supplied by the Original Hardware Maker. The Hardware makers do this to get cheaper prices for M$ OEM Product to save their customers money if they didn't do this they would be paying more for the Licenses and charging you more for the Computer that they sell.
The other thing here is that as there are only a couple of Versions of XP in either the 32 or 64 Bit products you can use a Install Disc of the same type to install your Computer with the Toshiba Supplied Product Key so there are options available to you but none of them are M$ responsibility they all are Toshiba's.
Col