Alright I dug into the source myself and found that the reason I can't sort is the document plugin.

More specifically, the search() method in addons/document/document.py (around line 105) overwrites the search results in order to see if the user is allowed to read the actual directory of the document.

My fix was to apply the same strategy as in base/ir/ir_attachment.py to return the filtered ids but ordered as requested:

ids = [id for id in orig_ids if id in ids]

Now I'm pretty new to openERP so if this is the wrong place to report this, could someone please let me know where to do this instead so it gets fixed upstream?

Here's a full patch (can't attach due to karma<30):

--- a/addons/document/document.py   2012-12-27 12:06:00.000000000 +1000
+++ b/addons/document/document.py   2014-01-18 15:18:33.000000000 +1000
@@ -85,14 +85,14 @@

     def search(self, cr, uid, args, offset=0, limit=None, order=None, context=None, count=False):
         # Grab ids, bypassing 'count'
-        ids = super(document_file, self).search(cr, uid, args, offset=offset, limit=limit, order=order, context=context, count=False)
-        if not ids:
+        orig_ids = super(document_file, self).search(cr, uid, args, offset=offset, limit=limit, order=order, context=context, count=False)
+        if not orig_ids:
             return 0 if count else []

         # Filter out documents that are in directories that the user is not allowed to read.
         # Must use pure SQL to avoid access rules exceptions (we want to remove the records,
         # not fail), and the records have been filtered in parent's search() anyway.
-        cr.execute('SELECT id, parent_id from ir_attachment WHERE id in %s', (tuple(ids),))
+        cr.execute('SELECT id, parent_id from ir_attachment WHERE id in %s', (tuple(orig_ids),))

         # cont a dict of parent -> attach
         parents = {}
@@ -108,6 +108,8 @@
         for parent_id in visible_parent_ids:
             ids.extend(parents[parent_id])

+        # sort result according to the original sort ordering
+        ids = [id for id in orig_ids if id in ids]
         return len(ids) if count else ids

     def copy(self, cr, uid, id, default=None, context=None):

Thanks! I was dealing with the same problem.