Rebuild the entire WordPress uploads folder

I have an unfortunate situation in which a client disabled Organize my uploads into month- and year-based folders which is what organizes files into a {year/month} folder hierarchy on the webserver. Now I have too many files in one folder for the server to handle. I'd like to move the files into folders again and update the db to point to the new file locations. Is there any way to do this (or get me a good part of the way)?