I'm surprised by your findings on the randomseed(). Analog pin 0 is actually leg 1 on the chip, which is disconnected. My thoughts were that worst case, even if it always returned the same value as that seed it will still generate a pseudorandom sequence, though it will have a sequence that will repeat every run. It isn't electrically connected to the LEDs so I need convincing it can be playing a part in flashing any lights.
analog 0 in actually pin 5 on the Attiny... try it with the fade sketch. 
I will try tomorrow the thing you said about the fading and also the random generator.