When dealing with a solution level folder that has been removed for some reason, and now needs to be added back, open the .sln file in a text editor like notepad++.
Find your "FolderName" in the section that looks like this...
Project("{2150E333-8FDC-42A3-9474-1A3956D46DE8}") = "NewFolder1", "NewFolder1", "{73ED84FC-F250-4CCC-B267-34CEB67F2883}"
EndProject
Delete from "Project" to "EndProject" ONLY for the specific Project/Folder you're having trouble with.
You may get a message in VS2012 that says your solution has been modified by an external source. Choose the option to "Discard" your changes for the external changes. Lastly, add your solution level folder, and add your project(s) to that folder as existing items, drag/drop them, or copy and paste them, according to your preference.