I'm not sure what is going on . I made a simple report as you describe and sort by Start date - it works without issue. I do have my date format just showing the numeric, but when I switch the date format to show Day of the week - it still works as expected.

Do you have maintain hierarchy enabled? Why are you showing project? Is this a consolidated project? If so, I am not sure it will sort outside of a single project. In other words - I'm not sure it will intermingle tasks between multiple projects.