Du musst dem GCC noch sagen, wo er nach den Headern suchen soll.
Schau mal nach, wo die bei dir sind, ich hab sie unter
/usr/avr/include
Das Verzeichnis musst du dann noch dem GCC übergeben.
Außerdem brauchst du noch das Verzeichnis für die libs, sonst kriegst du später noch ein paar Fehler.

Code:
avr-gcc -I/usr/avr/include -B/usr/avr/lib -g -mmcu=atmega16 -Wall -Wstrict-prototypes -Os -mcall-prologues -Os -c test.c