Ach! I have it! The loops are the wrong way around. In your code you are adding to i, even if you don't send that value to the LED. In other words, you only send the updated "i" at intervals of "interval". Hence it jumps in brightness in large gaps.
This fades up nicely, relying on the byte value in "brightness" to wrap around at 255:
const int LED = 3;
const unsigned long interval = 10;
unsigned long lastcheck = 0;
byte brightness;
void setup()
{
} // end of setup
void loop()
{
if (millis() - lastcheck > interval)
{
lastcheck = millis();
analogWrite (LED, brightness++);
} // end if time up
} // end of loop