Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$
Your summary of the proof of undecidability is not accurate.  Your specification of $\overline{A_{TM}}$ is not correct.

For a reasonable exposition of the proof, see https://liacs.leidenuniv.nl/~hoogeboomhj/second/codingcomputations.pdf particularly the beginning of Section 1 and Section 3.

The intuition is not easy to convey, as the proof is not entirely trivial.  But here is the core fact.  Let $v,w$ be two configurations of a Turing machine.  Write $n(v)$ to be the next configuration of the Turing machine after a single step of computation, if you start at configuration $v$.  Define the language

$$L = \{v \# w^R \mid n(v) \ne w\}.$$

Then the key fact is that $L$ is context-free.  This takes some proof; proving that is a key step in the proof.  However, that's the answer to your question: $L$ is context-free but not regular.  As a result, we can reduce the halting problem to $ALL_{CFG}$ but not to $ALL_{REX}$.

I have skipped many steps to give you an overview of the main idea.  You will need to read the full proof to fill in the details.  I suggest that you next read and understand the proof, with this perspective in mind, and then revisit what I've written here.  Hopefully that will help you understand why the proof holds for context-free languages but would fail for regular languages.