Hello Ollie,
I'm not sure exactly what problems you may be having doing this, but after you click on New and Folder, you will need to click on YES in the UAC prompt to approve it first. It should then create the New Folder for you waiting to be renamed.
If you do not see this, then see if this may be able to help. It is the same for Windows 7 as in Vista.
New Folder - Vista Forums
Hope this helps,
Shawn