Same problem here..but different solution.
Yes removing the password protection works.
However one can also select "Personal Macro Workbook" as the place for
storing your macros when you record one.

After saved there it will be available for al your workbooks, as the default
macro storing file opens hidden everytime you open Excel (PERSONAL.XLSB).

Still for the macros to work on your sheet one will have to UNHIDE the macro
workbook (PERSONAL.XLSB by default). Simply open and close the Macros list
(So, yes there is a bug here) and then the macros will be functional on all
workbooks.

This would be a aorkaround if one need to keep the file password protected.

"Andrew B" wrote:

I have just encountered this problem for the first time on a
password-protected workbook (originally converted from Excel 2000) where the
macros worked a month ago. Removing the password enabled the macros. I see
there was an update to Office 2007 two weeks ago, which appears to have
introduced the problem, though previous posts are older than this. Perhaps
Microsoft have extended this 'feature' in the recent update?