I am also experiencing this problem. I can only upload new code when the ethernet shield is removed. This is with a non-official ethernet W5100 based board. When the shield is in place, serial monitor does work, but upload does not. It doesn't give back any error other than a timeout.
I do find the recognition of the mega 2560 board by my laptop to be quirky. Sometimes I have to shut down the IDE before plugging the usb cable in, for it to be recognized and not show "com port not found" error.