I finally got my 2560 up a running just recently, and I feel your pain. The symptoms you describe are similar to what I saw. Here is a very long and boring story about what worked for me under Windows 8. Some questions:
-
Do you have rev 3 of the Mega2560 board? Look at the "Board Model" screened on the underside of the board.
-
Are you using any kind of ISP (usually another USB gadget like the AVRISPmkii) , or is the Mega2560 just plugged into USB cable?
-
Do the RX & TX leds blink when you try to upload?
-
Where did you purchase yours? Mine was from Digi-Key, and it was completely uninitialized.
Because you're able to begin an upload, I'll assume that the board has identified itself to the Mac, and appears as a valid COM port to the Arduino IDE. Couldn't help you there... 
If I were to guess, I would say that you have rev 3, and that you're just using a USB cable to upload to the Mega2560. If that's true, then that probably means that the USB interface chip, an ATmega16u2, has not been correctly initialized. This is an extra processor that handles all the USB "stuff" so the ATmega2560 processor has more time and space to do fun things. The two processors talk to each other, sometimes with data that comes over the USB cable, and sometimes with the special STK500v2 protocol when a new program is being uploaded. They talk to each other over the RX0/TX0 data lines, which are also accessible on the edge of the board.
I suspect that you are not really uploading anything to the board... it is just running the same, original sketch because the upload fails.
I further suspect that the ATmega16u2 and the ATmega2560 are not really talking to each other, even though the Loopback test works! This is confusing, because the loopback test only tells you that the Mac-to-USB-to-ATmega16u2-to-loopback-to-ATmega16u2-to-USB-to-Mac path is working. It does not tell you whether ATmega16u2-to-ATmega2560 is working.
In my case, the ATmega16u2 was running 8 times slower than it was supposed to -- the ATmega16u2 was communicationg at 1200 baud, and the ATmega2560 was at 9600 baud. If you have access to a Scope or Logic Analyzer, you could look at the RX0 line to see what the ATmega16u2 is transmitting.
Unfortunately, the only way to fix this is to reprogram the ATmega16u2 chip. There is an extra 3x2 array of pins near the USB connector on the board. This is called an ICSP header. An ISP can connect to this header for uploading new programs to the ATmega16u2. Another ICSP header is over by the RESET switch, and it is used as an alternative way to upload sketches to the ATmega2560 processor with an ISP (in the IDE, use File -> Upload with Programmer).
If you have an ISP (or another Arduino that can act as an ISP), instructions for reprogramming the ATmega16u2 can be found at the end of my post, in a suggested Restore section.
If you don't have an ISP, you will have to either buy/borrow an ISP or return the board.
There's a lot of assumptions here, so my free advice is probably worth exactly what you're paying for it. 
Cheers,
/dev
P.S. After posting this, I wondered if the 2560 bootloader needs to be programmed as well. The fact that LED "L" comes on means that it probably has something, but it wouldn't hurt to start from a known state. Also requires an ISP, though.