I'm using a 328-based Duemilanove which only has 2kB of SRAM, which is where literal strings are stored unless you move them into flash memory. The Mega has 8kB of SRAM so you would need a lot of those strings to cause a problem and if you are exeeding the limit of SRAM in your Arduino then it should fail on both WIndows and Linux.
But, it might be worth trying this just to see if it helps.
Wherever you have a statement like this:
Serial.print("whatever"); // or .println
change it to:
Serial.print(F("whatever"));
The F() macro puts the string in flash memory and the Serial.print/println statements will print it from there.
Pete