No BIOS or POST screen sounds bad... could be a fatal system board or similar failure.
Or it could be a hard drive or other accessory is taking too long to respond, and the computer is waiting for it. Or ram. Or power. I'd try removing accessories to troubleshoot if it's something easily replaceable that's the problem. With no hard drive it should still boot to something, a message saying "No OS available" or similar, and you could get to the BIOS if it's working. There's not much to easily remove from a laptop except the battery & anything plugged into it, then the harder to reach hard drive & dvd (I wouldn't suspect the dvd to be the problem but never know), then the RAM (if there's 2 or more take one out & see if it works then, or works with only 1). Not too sure how to troubleshoot a laptop power supply without unplugging it & trying another one.
At least that's what I'd try. And if it still won't boot to BIOS after there's nothing but a ram stick in then it's probably the system board or something that can't be removed easily. There should be some more detailed laptop troubleshooting guides in a web search, maybe even specific to a Toshiba laptop.
If it's still under warranty that's always a good option. But don't break any of the "do not break or no warranty" seals/stickers.
I'm guessing that seeing a GRUB menu is not the normal way your laptop boots in to Ubuntu, so this could also be a software/Ubuntu problem. But you should always be able to get to the BIOS screens no matter what's on your hard drive. And if you remove the hard drive that would eliminate any Ubuntu problems and you'd at least see if your laptop still works and can get to POST/BIOS.
Thinking about it getting worse after cleaning the fan with compressed air... It might be possible that these are overheating problems, but I think the laptop's more likely to shutdown if it gets way too hot.
It's possible that some big bunnies of dust got blown deeper and lodged in somewhere and are causing it to overheat faster now too. But if you can still feel the fan blowing out air like normal then it's probably not a "blocked air" problem.
If the laptop were completely cold and then you turn it on, I'd imagine you could at least see a POST and maybe get into the BIOS before it overheated... but if the heatsink has come off or something then the cpu could overheat in a few seconds.