Kant isn't easy, and I'm no expert. But let me try a slightly different turn, which may help clarify.
As noted, utilitarian or consequentialist ethics is concerned with the outcome of an action. The action is good if the consequence is good. But then, as you noted, you have to define what you mean by "good" and so on in an infinite regress of relative means and ends.
(As an aside, one reason Kant rejects this view is that it assumes we can actually predict outcomes, while in reality life is full of unintended consequences. And because of its relativism. You can always move the goal posts and redefine the good or appeal to simple majorities.)
Kant was deeply concerned with moral law in the emerging world of science and utility. His whole approach sought a path out of such relativistic dilemmas, developing a complex, utterly original philosophical set of critiques.
He assumes, in some sense, a human subject that is rational and "free" to make moral choices. Rather than point to "evidence" or appeal to axioms, he painstakingly demonstrates what "must already be the case" for such a being to exist. A moral being must have a capacity to both know what is "good" and yet be able to freely choose. What sorts of mental relations and categories must be universally the case for this to be so in the first place?
So, Kant is looking at the total logical makeup, relations, and categories that must exist "universally" for all such creatures, all "rational beings." He is not concerned with the "psychology" of this or that person or "sociology" of this or that society.
He uses the term "hypothetical imperative" to describe actions that are means to given ends, as in utilitarian "reasoning" towards some goal. If...then. But the "categorical imperative" is a rule that must be consistent with the very existence of "reasoning" itself. It must be "universal" for all reasoning beings and not contradict the categories of thought necessary to the very act of reasoning.
Morality is not so much about external ends, good or bad, but about the internal logic and coherence of a "being that can reason" and all that entails. Lying, for example, is always wrong even if it saves lives, because the act of lying "logically" contradicts the very basis of a lie, which is premised on the default assumption honesty that makes language possible to begin with. If everyone lies, that is, no one could lie.
Now admittedly, this is not a very useful guide to actual ethical choices. Nor is this a very satisfactory explanation. The only real and complete answer to your question pretty much entails all of Kant. But the way to start think about it is that the CI is justified more by internal coherence with "reasoning" than by the "reasons" given for some specific end. It is that ultimate "reason" for which reasoning itself is the end.