ok, tracked it down - it's a bug in binutils. It's related to the fact that the mega 256 target board uses the -Wl,--relax linker option since it has greater than 128 kB of memory [1,2] which somehow started causing problems once code was compiled with gcc 4.7.
For now it is a Debian only bug, but if Arduino moves to gcc 4.7 they will have to handle it. Debian is working on it here:
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=686173
[1] Google Code Archive - Long-term storage for Google Code Project Hosting.
[2] 13612 – segmentation fault with --relax option, avr target