When you right-click on the Desktop and click New, the Folder entry may be missing from the sub-menu.
Although the cause for this issue is unknown, the resolution is simple. Visit the File association fixes for Windows Vista page in this site and download the Folder association fix (folderfix_vista.zip). Unzip the fix and extract the .REG file to the Desktop. Right-click the .REG file and choose Merge. Note that you need to be an administrator to apply this fix.