Sorting doesn't work properly

Sorting seems to be working in mysterious ways. I am trying to sort by Node: Title and I get unexpected results.
I have also tried using CCK custom field to sort it using this, but it is also not working properly.

Sorting works fine when selecting a different View Type, such as Table View.