I inserted the following two lines in the arduino-1.0.1/arduino script, forcing the compiler to pick up the correct #include files:
CPATH="${APPDIR}/hardware/tools/avr/lib/avr/include"
export CPATH
Put that right before the last line which runs the Java runtime and we will be fine. I think I solved my own problem, and hope to solve someone else's in the future.