Is there a way to change the sort order of the "shop by" attributes?
I tried changing the order in the attribute set, but that does not seem to work
You set the sort order on the individual attribute:
admin > catalog > attributes > manage attributes > attribute
In the attribute you edit the "Position" setting
Remember to re-index afterwards.