Yeah I've read that I should use a separate power supply, but there was no time to do it like that. If not enough power is available, I would have expected them to simply not run. That they run absolutely unpredictable AND have issues when coupled with a different power source supposedly providing the same voltage (and god knows what else :P) ... I truly didn't expect this.
So what you're suggesting is that the random colors & flickering can be solved with a separate power supply for the LEDs alone?
What about the resistor in between Arduino data pin and LEDs, is that something to consider? I've read mixed things on this topic.