When you right click on the desktop or on My Documents, do you see "New" on the menu?
If you open Windows Explorer and click on My Documents (in the left column), does your Explorer window show a button titled New Folder at the top (under the Menu bar)?