mellis:
Do you have the same problem with Arduino 1.0? Testing it would help isolate the changes that caused this problem to occur.For example, in Arduino 1.0.1, we added the "--relax" flag to the linker options, which helps with large programs (Google Code Archive - Long-term storage for Google Code Project Hosting.). It's possible that the issue you're seeing is a side effect of that change, for example.
FYI I had the exact same problem and using Arduino 1.0 fixed it.