Yeah, I've tried that too. Made a mistake in my first post, should have said I have Selection of Random New Products set to 9.
I have tried different settings, but it just shows the same products, just randomly. ie: I set Selection of Random New Products to 9, I see the same 9 products randomly displayed, I set it to 15 I see the same 15 products randomly displayed.