mellis: I'm using 0012 and 0013 exclusively on Windows. [EDIT: irrelevant stuff deleted.]
The compiler that comes with Windows 0013 is avr-gcc 4.3.0, which is the one that the avr-libc developers advised steering clear of. But I speculate that the reason I and other Windows users don't see problems like the ones above is that we don't build our own avr-libc -- we use the one in the distro.
Whether any of this I've just typed is related to etracer's issues with AFSoftSerial and NewSoftSerial is just speculation.
Mikal