The file you emailed to me was the deck again, not the entire collection (it should be
collection.apkg). I had a look at the deck itself and it seems to work correctly for me. Both on the desktop and AnkiDroid, the new card order follows the creation date and they appear in the same correct sequence on both devices. There is nothing wrong with the deck.
Have you tried doing a full sync of the collection from the desktop? See if that fixes things for you. (Tools -> Preferences -> Network -> On next sync, force changes in one direction).