You can move around with some data.
You could use more 'F()' macros with the print() and write(). That can be with the Serial.print() but also with other library functions that use the stream class.
Are you very sure that the arrays are in flash ?
Can you show your code for the arrays and variables ?
If they happen to be placed in ram, you have ram overflow.
You could implement the function for available ram, http://playground.arduino.cc/Code/AvailableMemory
Version 1.0.4 and 1.5.2 of the Arduino IDE have improved code for the bootloader. You could rewrite the bootloader with a programmer or another Arduino (Arduino as ISP).
If you don't use too many libraries, and you upload or send me the code, I could try to make it work. I have already the newest bootloader on my Mega.