Just thought I'd put this up here for anyone else… if you're UPGRADING to MT 2.5 – and you were previously using MT-Search… It isn't actually mentioned in the upgrade instructions themselves… but you will need to do a few extra (albeit) easy steps to get search working again. Just look in the REGULAR instructions for MT about "Public Search"… and "Alternate Templates" there will be a section in there that explains what you need to do.
(Oh, and btw – search is now working again on this blog