I have this strange issue sinds last week.
I name my files by date.
So if I create a new file and the date is 2012_01_01_name_of_file.pdf my overview page puts it on top of the list.
The shortcode I use is: [downloads query="category=3&order=DESC"]
This works partially because everything I did before last week still get's orders DESC but the new uploads not anymore.