Have you checked with Toshiba*? The non-Intel chipset in your system may not support anything above a Celeron processor. Even if it does, you may need a BIOS update from Toshiba in order for your system to recognise the upgraded processor.
If you want a list of Socket M processors, like the Celeron M 410, you can start by looking at this link: http://ark.intel.com/ProductCollection.aspx?codeName=2673
I haven't found any Socket M processors in my research that support the 800 MHz FSB. The max seems to be 667 MHz FSB.
Intel Customer Support
*Other names and brands may be claimed as the property of others.
Update to my original post. I installed both, a Yonah and a Meron dual core processor and they both work. Specifically, I install the T2700 Core Duo and the T7600 Core 2 Duo. The T2700 was a simple replacement. When I installed the T7600, Windows had to do install an update. Other than that, there were no other issues. As for the memory, the 800 MHz memory would work for awhile, but failed randomly. I had to use the 667 MHz memory for a stable environment. I am still using the T7600 in my Toshiba today.