The default sorting the alphabetical. But if someone changed the order using the arrows, then the new attachments are added at the top and the alphabetical order is not ensured - this would be a performance killer because you would need to go through all the attachments, find a place where to put it and then change the order value for all the rest of the attachments.
SO, check the CMS_Attachment table for this page (AttachmentDocumentID = your page ID and AttachmentIsUnsorted = 1). If the AttachmentOrder column has an integer number value, then this is used to determine the order. If it is null, alphabetical order is used. So, you can reset the values to null and then restart Kentico - now the attachments should be in alphabetical order again. And then tell the editors to not to use the sorting arrows :)
UPDATE [dbo].[CMS_Attachment]
SET [AttachmentOrder] = null
WHERE AttachmentDocumentID = XY