Well, if you are having difficulty with the action a workaround (if you want truly random colours) could be to use a random float between 0 and 255 three times, compile that into a colour variable and use that instead?
it'd give you truly random though and might not be very visually appealing depending on the aesthetic you're aiming for... but hey, if one method doesn't work another one might.
But yeah... i've not encountered any issues with the random colour action personally so maybe can you share a screenshot of how you have it set up?