(disclaimer: I have nothing to do with Sesame)
From http://www.w3.org/TR/rdf-sparql-XMLres/#head it states:
"""
The order of the variable names in the sequence is the order of the variable names given to the argument of the SELECT statement in the SPARQL query. If SELECT * is used, the order of the names is undefined.
"""

It would seem that Sesame's behavior is correct (in that the behavior is undefined).

I dont care what order they come back in - I just care that I can map the results to the right variables.
I.e. I'm not after the same order as the one they appear in the triple patterns, but i'm after consistency between the arraylists returned by evaluate and the names returned by getColumnHeaders.

FWIW in Sesame 2-alpha-4 we have introduced a completely new QueryResult interface which explicitly works with variable bindings. getColumnHeaders() is replaced by QueryResult.getBindingNames() and one gets actual values by giving their binding name (rather than an integer index). So solution tuples are no longer ordered with respect to the original query.