If I create a bunch of cube primatives, I can't colour them differently to each other as I only have one shared material. I'd like to be able to create a new material so that I can then paint it on some of the primatives without impacting any objects already in my scene.

You can create a new material at "Materials > New Material..."

Yep, thanks. I'll amend my request to say "can this please be a button on the materials dock to make it more intuitive" :D