Satch - I am having the same problem with a macro I'm trying to record. Thanks to Peter's link to the Microsoft support web site, I now know what the issue is (thanks, Peter!).
I have a problem with Microsoft's solution - simply don't record a macro in which you are entering more than 255 characters within a cell. I hope this issue is resolved in Excel 2007!
I resolved my issue by breaking up the formula into several columns for the purpose of the macro. While the columns serve no purpose other than flags or control mechanisms for my 'IF' statements, I can easily hide these columns within the program of the macro.
If there are other ways around this problem, I'd like to hear them as well.