There is no paradox as long as you realize that, when you say "all adjectives can be categorized as autological or heterological", the "or" is not exclusive.
To explain this a little bit better, let's try to describe this using math syntax. Let's call $f$ a function that returns the relevant description of a word. So $f($"short"$)$ is "short", and $f($"long$)$ is also "short". Then if $f(a)=a$ then $a$ is autological, while if $f(a)\ne a$ then $a$ is heterological.
Using "autological" in this formula works fine because $f($"autological"$)=$ "autological". However, what about $f($"heterological"$)$? If $f($"heterological"$)\ne$ "heterological", then it is heterological, and if $f($"heterological"$)=$ "heterological", then it is autological. This is where the apparent paradox comes in, but what this really suggests is that our function $f$ is poorly defined!
Obviously, words can be described by more than one description - for example, "polysyllabic" is both polysyllabic and long (or medium-sized, if you want). So why not have $f$ return a set of descriptions of the word? This would make an autological word one for which $a\in f(a)$. A heterological word could be defined either as $a\notin f(a)$, or one for which $\neg a\in f(a)$, where $\neg a$ is an antonym of the word. Assuming the first definition of heterological, if "heterological" $\notin f($"heterological"$)$, then "heterological" $\in f($"heterological"$)$, so we should use the second definition.
There's still something a little weird here, but it is no longer self-contradictory. Suppose "heterological" $\notin f($"heterological"$)$. Then it is not autological, and because "autological" $\notin f($"heterological"$)$, it is also not heterological. However, suppose "heterological" $\in f($"heterological"$)$. Then it is autological, and since "autological" $\in f($"heterological"$)$, it is also heterological. The logic in both cases is circular, but neither one actually results in a contradiction.
So while this does not answer the question of whether "heterological" is heterological or not, this does resolve the paradox - it is either both heterological and autological, or neither. I believe that we should consider it to be both, making it an auto-antonym. Also, it suggests that we refine the definition of "heterological" to be more like "it can describe something that it is not".