[gallery] works for me, but I am using my own functions to process it. However, when uploading the images go into reverse order, I have filed a bug about this here: http://trac.wordpress.org/ticket/7315
When you view the gallery tab, are there numbers in the ordering boxes? After uploading you have to drag at least one image to initiate the ordering field. IMHO the ordering should be pre-filled in based on the order files were uploaded. This would remove the problems with them showing up in reverse. If you don't have order numbers in the boxes, try ordering by ID or title as a temporary solution until this is resolved.
Edit: the other temp fix is just to drag your images into reverse order, i.e. first one at the bottom.