I forgot to mention that we also tried the boards.txt fix - changing the protocol to wiring and this did not help. We even restarted the Arduino IDE several time with the wiring protocol line but still no action.
xvjeko - this is very interesting and we are all waiting for David Mellis to throw some light on this. What you have described sounds like one of two things - bad soldering or incorrect fuses in either the 2560 or the USB chip. Since all the boards were tested at the factory, something must have happened since. Bad soldering can cause this -talking about intermittent open circuits caused by a poor solder mix or not enough paste. Remember that solder paste must always be kept in a fridge when not being used. The other option of having fuses not set correctly can also cause intermittent operation - such as the brown out enable not turned on. A third scenario is faulty Atmel chips which is a small possibility -luckily Atmel is very open about Erratas do these can be easily checked.
Anyway, sounds like a lot of Arduino users have the same problem, so a workaround would be nice.