Some people need only to edit, some people like to drag and drop. For the people that drag and drop frequently are usually artist, fashion, or photographers who want to have a image resume for their galleries. Usually they dont have thousands of albums, as their are more selective with their work and how its perceived to the public eye.
On the other hand you have companies that upload galleries daily like myself who has 15 photographers that cover 30-50 events a week, with about 200 pictures each album. We dont drag and drop order. We place albums in the order it was recieved/date of event.
A solution would be to give tab or button for type of album editing interface needed. Using drag and drop ajax interface, or plain php page with list of galleries and buttons to edit them.
Remember, the bandwidth intensive and time consuming ajax album edit page is not always needed. So the idea I suggest will help atleast half of your clients.
Now if someone wants to drag and drop thousands of albums in different orders, then I can help with that lol