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 (http://code.google.com/p/arduino/issues/detail?id=729
). It's possible that the issue you're seeing is a side effect of that change, for example.