Finally it seems I was able to get a working toolchain on gentoo/AMD64:
- emerge crossdev script 20120305
- applied patch to /usr/bin/crossdev from 377039 – sys-devel/crossdev-20110705: crossdev -t avr produces broken toolchain: cannot find crtm1280.o, skipping incompatible libm.a when searching for -lm comment 30
- used older version of binutils since newest version has a bug:
crossdev -t avr --b 2.20.1 - fixed ldscripts:
ln -s /usr/x86_64-pc-linux-gnu/avr/lib/ldscripts /usr/libexec/gcc/avr/ldscripts - fixed error with prog_char described here: Google Code Archive - Long-term storage for Google Code Project Hosting.
Now I was able to compile and run blink and DhcpAdressPrinter 
I will do some more tests the next few days and report back if this toolchain can be considered stable.
Thanks again to all who tried to help