If I determine the order of the reactants in a reaction without using a catalyst, and then use a catalyst, will the order of the reactants then be different?
Yes. It is possible for a catalyst to change the order of a reaction since it shows different path to the reaction i.e. reaction occurs through different mechanism. In the new path, rate determining step (slow step) may involve different number of reactant molecules.
For example, in case of reaction catalyzed on metal surfaces, most of the times, the rate does not depend on the concentration of the reactants at higher concentration since now it is surface area that governs the rate.