Looks like the bug reported has been fixed! I can compile the Ethernet library examples for a Mega 2560 or ADK on Debian Wheezy.
The problem was a bug in "ld" (binutils). It has been fixed. You need to download and install the brand new binutils-avr which is currently in unstable (version 2.20.1-3)
EDIT:
you are using Raspian, awesome. The official packages from arduino.cc therefore might not work for you (they are only good on intel/amd64 architectures). You'll have to wait until Raspian builds it. They will show up here:
http://archive.raspbian.org/raspbian/pool/main/b/binutils-avr/
and may take a couple of days. You can "apt-get upgrade" once it hits the repo there as well.