Hola,
si le das tiempo para que recorra los distintos niveles (por ejemplo, 2 segundos cada vez), el fading funciona
long inicio;
void loop()
{
digitalWrite(led, HIGH);
delay(500);
digitalWrite(led,LOW);
delay(500);
inicio = millis();
while(millis() - inicio < 2000L)
{
analogWrite(led, brightness);
brightness = brightness + fadeAmount;
if (brightness == 0 || brightness == 125)
{
fadeAmount = -fadeAmount ;
}
delay(30);
}
}