To be honest with you, it didn't seem like this should be allowed in XP to me. It seems like a fix almost. The reason I say that is because if you turn off the Create Folder functionality in the document library settings, it disables it from the web browser but still allows "New Folder" in Windows explorer. So I figured they disabled the "New Folder" button entirely to correct that issue.
However, it appears that the "New Folder" button has only been taken away if you do the "Save As" from within Office and the dialog detects it is a SharePoint site. In other words, if you launch Windows Explorer outside of Office and type in the address to your document library, it still looks and feels like a normal folder and you can create a folder just fine. If you type in the address from the Office Save As dialog, the dialog looks more "SharePointy" and the create folder button is gone.
So here is one workaround. If you map a drive to the document library following the instructions at http://support.sherweb.com/Faqs/Show/how-to-connect-to-a-sharepoint-site-using-webdav-sharepoint-2010, then you can specify z: for example in your Office Save As dialaog and the New Folder button will appear. I did just that, and it added the folder. Strange thing, though, when I saved the document to a folder I created through the dialog I got an error from the Microsoft Office Upload Manager telling me that the document could not be uploaded. I'm using Office 2010. If you are using a previous version this may not happen to you.
Incidentally, I think this workaround is also an oversight, because if I disable the ability to add folders to my document library I can still add them in Windows Explorer through the New Folder button using the mapped drive. That's disappointing.
A total side note, but as I was looking into this I came across a great article that explains the difference between using WebDAV and FPRPC with SharePoint. You may want to give it a read for background information before mapping a drive. http://blogs.technet.com/b/manjesh/archive/2010/01/03/all-about-explorer-view-in-sharepoint.aspx