It does not sound like this has anything to do with avr-gcc and avr-libc. If the other programmer is working, then the program is being compiled correctly. Have you tried the code with the USB/bootloader?
Just a warning: Be careful about the version of avr-libc you downgrade to. You could be adding more problems to your situation.
When you went back to a previous version, did you back up to avr-libc-1.7.0, that has a bad delay() bug?
Or avr-libc-1.6.9 that won't start the serial function?
I think v1.6.8 is the only other recent version that works.