Now that's odd. I never noticed it before, but it appears you are correct: Align to Grid simply does not work in footnotes!
I have always thought the current way of adding Footnotes is a sort of dirty “hack” from the Adobe programmers. There are lots and lots of problems, such as not able to span or ignore columns, numbering is limited to the utmost basics, totally ignores text-wraps, etc. etc. etc. And, with CS5, it seems the programmers at Adobe got themself into even more problems with adding span-over and split-into column paragraphs (see elsewhere on this site for how big these problems are!).
Join our select little club of academic book-makers, and complain: Improve Footnotes Please (use the link in that discussion to send a formal Feature Request to Adobe).
As for your problem … All you can do is set the leading of the footnote text to exactly your baseline grid distance, and make sure the Minimum Space Before and all other dimensions are also in baseline grid distances.
(I'm fairly sure you made your default text frames already an exact multiple of baselines, so working bottom-up should not be a problem.)