Do your users know that the columns are sortable?
I ask this, because even though there appears to be a sort indicator on the first column, the users may not realize that they can click the headings.
What is the average size of the data set?
If, after a search, I get all of the information I need in a single screen of data, I might not be inclined to sort.
Why are the users who do sort using the feature?
 This is sort kind of related to the previous question. Not all users like to search. I've seen users just take the default data and sort 'n' scroll their way to happiness.
Is the data grid so painfully slow that the users never user it?
Is it possible that the users just don't like sorting because of the performance problems? As a developer who dabbles in UX, I'm not sure I buy performance as a barrier. Unless your application is performing huge aggregations every time they sort, there is no reason why you can't aggregate the data and then sort the result. You could even periodically pre-calculate the aggregations. The very presence of sort should not be an issue.