Update button is not updating anything

There must be an issue on your side, most probably a plugin which throw errors. You should check on the ajax call response, which should reveal more details.

You wrote: “You should check on the ajax call response” – where should I exactly check?

Try Firefox and FireBug add-on.

Thanks. I tried firebug and clicking the update button is giving me 200 OK status but the order of the posts are not changed.
As I wrote above, when I refresh the Re-Order page at the admin panel, the posts are ordered at the same order previously.

Possible there is another plugin or even your theme which overwrite the order, can you try to de-activate one by one to find which is the cause?

I did as suggested and there is no change. The posts order stays the same.
Is there any limitation in terms of number of posts? I have around 3500 posts in my blog.

Well that’s the problem, giving the large amount of posts on certain servers this will never complete due to php imposed limitations, either code execution or even the parse_str which may be limited to 1000.
You may want to increase the parse_str php variable value and the maximum allowed time execution. There are chances so you can’t do such updates, so a server migration may be required.
Or you can simply consider to update to Advanced Post Types Order which contain a different approach to avoid such limitations.