I had a problem like this with my ethernet shield and an EtherTen board which turned out to be caused by having updated my avr tool chain on my linux box to a newer one. I reverted the toolchain back to the older versions that were supported by apt (this is on Ubuntu 10.04) and suddenly my sketches worked and the ethernet data was sane again.
These are the package versions I'm running now:
avr-libc: 1.6.7
binutils-avr: 2.20-2
gcc-avr: 4.3.4-1