Realize this thread is quickly aging but thought I share my experience.
I ran into a similar problem by receiving the "avrdude: verification error, first mismatch at byte.." followed by unpredictable program behavior
I did some testing using the pgmspace library, where you can save data in the program memory area.
I found that my memory has a corrupt 128 byes .
if you try the following program, you may see the same for you.
The program will basically fill up your program memory with a pattern (01-pattern) and then play it back. If the memory is corrupt, it will show a different value in the output than the pattern provides. You can alter the first and last array entry to shift the pattern one word on a second run to verify there are not intra-byte issues too.
While not perfect, since memory fault could be where executable portion of the program gets dropped, it's not a bad little test.
Anyway, let me know if it helped. If anyone knows a way to address the issue I have, please let me know. in the meantime, I'm off to e-bay to buy a new ATMEL chip 
#include <avr/pgmspace.h>
//repeat the following array pattern until you max your program out to the maximum size
PROGMEM prog_uint16_t charSet[] = {
0x5555, 0xAAAA, 0x5555, 0xAAAA,
0x5555, 0xAAAA, 0x5555, 0xAAAA,
...
}
void setup()
{
Serial.begin(9600);
prog_uint16_t myInt;
long int lsize=sizeof(charSet)/sizeof(prog_uint16_t);
Serial.print("Size of array=");
Serial.println(lsize);
for (int i = 0; i < lsize; i++)
{
myInt = pgm_read_word_near(charSet + i);
Serial.print( myInt, HEX );
Serial.print( "," );
if ((i%(44))==((44)-1))
{Serial.println("");
}
}
Serial.println("Done");
}
void loop()
{
}