Hi! I had what seems to be a similar (identical?) problem.
Running a Mac with OS X 10.6.8 and a genuine Arduino Mega 128. None of my sketches would upload (although OK on another Windows-based system); always ending up with - "avrdude: stk500_recv(): programmer is not responding".
I found (from an old post) that I could work around by holding down (and keeping it down) the reset button until the programme size was shown in bytes of memory used, and then releasing the reset button.
This morning I have cured it totally (for now!) by: saving all my sketches; finding and trashing anything with a reference to "arduino" in the file name; re-downloading the software (and the few libraries I need).
This only took about 20 minutes going steadily, and now it works just "tinkaboo"!!
I hope this proves to solve your problem too!!
Regards,
Paul G