Hi, Odisej,
If you want ultra smooth random color transitions (and have enough free memory on your arduino), feel free to use my implementation of the Perlin noise algorithm. I'm working on a 5x5 RGB led array and I'm getting great results (well, at least for me) You can see the array in action at www.neuronasmuertas.com/britable and get the Arduino code at http://code.google.com/p/britable/downloads/list (britable 0.10.rar)
Best regards