I just found out that in my case the Plugin Simple Slideshow seems to be the problem. When I deactivate it, the problem is gone and the sorting functions works fine. So I assume that there is a JQuery conflict between the two plugins?!
Any thoughts on how to fix it? I really need both of the plugins to run on my WP 3.5 installation.
Or is there any other plugin, that simply generates a Jquery cycle out of the standard gallery inserted in a post?