Order of data transformation
As explained in Sorting a Paginated Record Set User Experience Expectation, and as illustrated there by the following order of data transformations:
You can see that both filtering and sorting come before pagination.
This means that whenever the order changes (sort), you should repaginate.
Back to page one?
Whether or not you should go back to page 1 depends on the context:
The case for
Concretely in your case, once on page X and the order changes, page X most likely refers to the previous user query, not the current one.
Most of the time people go to the next page because their query wasn't answered by looking at the first page. In this case, re-ordering the data means a new attempt to answer the query (ie, locate the desired data) and in most cases this means starting from page 1 all over again.
The case against
But this is not always the case.
Say the user wants to know what item is at position 22 (say which is the 22nd cheapest item), then throwing back to page 1 after sorting is NOT a good thing.
There are more examples in the comments.
So it all depends why the user is on any page other than the first one to begin with.