Hi
I know its a while since there was any update on this, but there are people still experiencing this problem - like myself! So after scratching around like everyone else, I seem to have found the solution on Microsoft's website - although their description is not a 100% match to my experience, I optimistic that it will work, but only time will tell. If others want to try it, go to:
Excel 97-2003 workbooks (.xls) display #N/A! for Analysis Toolpak functions
for some details, or directly here for the download:
Description of the Excel 2007 hotfix package
Regards
Mark