I have windows 7 and had the same problem a while back
New Folder re-appeared after following the instructions given in the Best Solution section of the following link, which was found from Google search.
http://www.tomshardware.com/forum/65027-63-suddenly-create-folders
Good luck.