Sorting is based on order date_added and download sort order sort_order
You can see this in the download class:
core/lib/download.php
Line: 473 and 517
ORDER BY o.date_added DESC, od.sort_order ASC ";
This indicates that you probably have some strange sort order set in downloads. If download sort_order is not set (0) it would sort by the date order created.
You can edit this code or suggest a solution that works for all or most cases.