@mellis, back when I was investigating the problem with the broken Ubuntu random() function, the guys on the avr-libc forum advised steering clear of the 4.3.0 avr-gcc compiler, which they characterized as "broken". I thought it was funny that that's the version we use with Windows Arduino. Perhaps it would be good to upgrade all the Arduino distros to 4.3.2?
Mikal