You might want to try cutting out the store altogether, and using a Grid with a dojox.grid.data.Objects model. I am using that method, for other reasons, but I have no problems with sorting, even with large datasets (500+ rows, ~25 columns in the data, not necessarily all of them shown in the grid. It does require a slightly different format to the JSON data, and you have to do the xhrGet/xhrPost yourself, but it is fairly straightforward. The JSON data should be structured as an array of objects conatining named fields corresponding to your columns, and depending on your requirements you could add the data request and grid population to the dojo.addOnLoad or to a button onClick handler, etc. As a simple example, if you have declared your Grid with jsId="myGrid" and set up your view and layout like this:

var myView = {
  cells: [[
    { name: "ID", field: "id" },
    { name: "Description", field: "desc" }
  ]]
};
var myLayout = [ myView ];
myGrid.setStructure(myLayout);

then your JSON data would need to have the format:

[{"id":1,"desc":"Item 1"},{"id":2,"desc":"Item 2"}, ... ]

and, assuming a simple GET request would work, your dojo.addOnLoad, button handler or whatever would need to contain code similar to the following:

dojo.xhrGet({
  url: "myPage.php?category=widgets",
  handleAs: "json",
  load: function(response, ioArgs) {
    myGrid.setModel = new dojox.grid.data.Objects(response);
    myGrid.refresh();
    return response;
  },
  error: function(errdata, ioArgs) {
    window.alert("Error: " + errdata.message);
    return errdata;
  }
});

If you want to get a little more sophisticated, you can make the data a sub-object in the JSON response, and use other sub-objects to pass messages, errors etc.

Simon