Project works on some boards. not others.

Hi, Here's the problem, One of my projects stopped working recently after I made some minor code changes. The obvious answer was that my code changes had screwed something up. However, after some investigations I've discovered that the project will work (i.e. compile, upload and run) on my other two Megas. Ok, so the conclusion now is that there's something wrong with the original Mega. I do some further tests and I've discovered that the original mega still works with all the other projects and libraries I've written in the last few years.

So, in summary, I've got a Mega that won't work with one specific project, but does work with all the other ones. when I say 'not working' I mean it compiles and uploads without problem, but when I run it I get no output for three or four seconds followed by some seemingly random numerals...

10111411411111458329997114100461051101051163210297105108101100
83683210111411411111458321,0

Which look like nothing the project is supposed to generate. (not sure if this is relevant, but when I get this error, it's always the same series of numbers)

The only thing that's different from this project compared to all my others is that it is larger than the rest (compiles to about 130k), my best guess at the moment is that there's something wrong with some of memory, the smaller projects are working because they don't compile big enough to populate the dodgy memory. Does this sound plausible, or am I missing some alternative explanations? Are there any self-test routines I could run to exercise the full arduino memory and confirm my theory?

Mega has 128k of flash memory to store sketch, less the bootloader (4k). This is the expected (more or less) behavior for a 130k sketch. The mystery is how it works on any Mega!
Plus, the loader should complain, either that the sketch (.hex) is too large, or failed to verify (I say "should" not "will".)
There is (almost) always a way to make your sketch smaller. Doing that usually requires an understanding of what the compiler emits.

when I compile it says...

Binary sketch size: 128836 bytes (of a 258048 byte maximum)

I should have specified more clearly - I'm using a Mega 2560, maybe there was a earlier version with a smaller memory?

There is a mega 1280 and 2560, 128k / 256k flash respectively.
If you have a lot of flash strings and/or PROGMEM data, there are a few things to do.

Most built in PROGMEM functionality is tied to pgm_read_xx_near().
The near ( 16bit ) addresses can only read the first 64k words ( 128k bytes ).
Far addresses ( 24bit ) can read the far memory.

So if you use PROGMEM ( F() macros included ), then they will be pushed above this boundary when your sketch gets large.

What you need to do is move some PROGMEM data into far memory.

You can replace PROGMEM with 'attribute((section(".fini7")))' and the data is placed at the end of your program.

const char c[] PROGMEM = "NEAR PROGMEM VALUE";

const char d[] __attribute__((section(".fini7"))) = "FAR PROGMEM VALUE";

//Read first character of c:
char tempc = pgm_read_byte_near( &c[0] );

//Read first character of d:
char tempd = pgm_read_byte_far( &d[0] );

This is a complex subject, there are many threads ( some good ones too ) addressing this issue.

If this isn't the issue and its purely due to large code, you will have more reading to do, as the 'trampoline' and vector jump table must remain in lower memory as their pointers cannot reach the far memory either.

Lots of fun. Hopefully you haven't reached these boundaries yet.