After debugging all the possible values at runtime using GetProceduralPropertyDescriptions() I found that the random name I wanted was $randomseed

This works!

Random.Range(0,30) will return the same value in the same frame/tick. So you can put this in a coroutine and lag a bit by waiting for ms.. or end of frame.

OR better

Set the seed at each iteration

UnityEngine.Random.seed = i++; // or some incremental value

http://docs.unity3d.com/Documentation/ScriptReference/Random-seed.html

var instanceMaterial = instanceGameObject.renderer.material as ProceduralMaterial;
instanceMaterial.SetProceduralFloat("RandomSeed", Random.Range(0,30));
UnityEngine.Random.seed = i++;
instanceMaterial.RebuildTextures();

I dont think that the random element is really the issue, as before now I have set the random seed to just be i and it still doesn't work. I think the problem is down to how im setting the procedural value. I also have a color component which when set seems to remove all color, so this question is more around the correct way to interact with setting the procedural values.

(Although it is interesting to know the limitations on range, I am seeding it using the itteration count, still have the issue)