One possible response would be to take this on board, and develop a broader theory of justice within which utilitarianism is but one part. Perhaps the first priority would be to compensate those with special claims, and only afterwards engage the utilitarian principle in distributing the leftovers. A pluralistic theory of this sort seems a viable option.
But many utilitarians would be unsatisfied with this response. They would rather deny that legitimate claims can be made prior to utility calculations. Justice is whatever the utility calculations yield. Only by this method is each person counted for one, and nobody for more than one. The utilitarian thus denies that anyone may legitimately claim to be 'more deserving' than any other.
Desert skepticism can be motivated by considerations of ultimate responsibility. Nobody gets to choose their natural talents, so it would seem odd for justice to require that they get rewarded for their luck in the 'natural lottery'. And the inclination to expend effort is likewise a natural character trait which has its origin outside of our control. Even granting some element of free will, we're led to Roemer's account, whereby a natural slacker who puts in some slight effort is held to be more deserving of reward than someone who is naturally hard-working.
A third alternative is to reject my framing of the issue, and try to incorporate prior desert-claims into the utilitarian calculus. Thus Rescher (following C.D. Broad) distinguishes between the 'immanent' and 'transeunt' goodness of a distribution or state of affairs:
[T]he immanent goodness of a hypothetical universe is fixed by the amount of the goodness in it, and its transeunt goodness is fixed by the amount of goodness of it... these two things are not to be identified. (Rescher, Distributive Justice, p.51)
On this view, a state of affairs where the good are rewarded and the evil punished might be of greater (transeunt) value than another which merely contains more value but in a less just distribution. However, this approach makes justice prior to - and part of - utility calculations, and thus cannot be used to provide a utilitarian theory of justice, on pain of circularity.