I was "playing" with the ObjectDataSource's example from Part 2 when I realized I didn't enabled client callbacks for paging and sorting. I set GridView's EnableSortingAndPagingCallbacks to true and tried it. To my surprise, it didn't work! I was confused because I had tried it that in the past and it worked without any problems so it made no sense that it wasn't working now.
Of course the first thing that comes to my head in those situations is: "There's a bug in GridView's implementation". The reality is that 95% of the time it's my own fault but one never finds himself guilty until proven wrong!