How can I change the order of messages in Mail for Lion?
Just above the rows of emails there is a dropdown that says "Sort by"...

This can sort by date, flags, mailbox, etc. 

At the bottom of this list, you can choose to have oldest or newest messages at the top. Check to make sure you have newest selected.