I have also had this problem on and off over at least the past year (but not recently- hold that thought). Not only creating folders but renaming folders; any folder update operation done from the explorer tree. Edit: in every case I had no delay using Windows Explorer, similar to the experience of others here.
I also have some mapped network drives although I do most of my PM work on a local drive. The performance problem was on the local drives as well as, I guess, network drives although I don't add folders to the network mapped drives very often. I noticed that sometimes, but not always, I could eliminate the performance issue by simply closing the "My Network Places" branch at the bottom of the explorer tree. If My Network Places was open then the delay occurred, even if it was only open one level and even if no folders from that branch were open as a contact sheet.
At some point I figured out that if I rebooted the machine the problem often or always went away. I don't reboot my working machine (laptop) very often.
Later I found that disabling Kaspersky Internet Security would resolve the problem, and turning it back on did not cause further delays. From that I decided that Kaspersky was involved, and maybe only when it had run for a long time without a machine reboot (I don't turn it off unless I am doing problem resolution work).
About a month ago I updated from Kaspersky 2009, I think, to 2011. I have not had the problem in the last month, nor have I been rebooting frequently but I don't keep mental track of that so hard to say if K2011 fixed whatever it was doing.
Now with Kaspersky 2011 installed, my PM problem may be solved but my Outlook 2003 process NEVER shuts down, which means I can never get a good cold backup of my outlook mail files without rebooting. Which just goes to show that these AV programs are all evil
The main point here is that the problem may not be specific to Norton, in the case anyone else has this problem. If I get it again I'll bug Kirk for that debug version