What is a little confusing here is that the scalar multiplication is being written in the opposite of the standard order. In other words, given a real scalar $s \in \mathbb{R}$ and vector $v \in V$, the notation for scalar multiplication used here is
$$ vs \text{ instead of the usual }sv. $$
The reason for this is the following: First, a standard convention for matrices is to use the superscript as a row index and the subscript as a column index. Second the standard convention is to write the basis of a vector space using subscripts for the index. This means that you can write a basis $(e_1, \dots, e_r)$ of a vector space formally as a row matrix,
$$ e = \begin{bmatrix} e_1 & e_2 &\cdots & e_r \end{bmatrix}. $$ Then, any vector $v$ can be written as a linear combination of the basis vectors. The coefficients $c = (c^1, \dots, c^r)$ are written using superscripts. This allows the formula for $v$ to be written formally as matrix multiplication:
$$ v = e_1c^1 + \cdots + e_rc^r = \begin{bmatrix} e_1 & \cdots & e_r \end{bmatrix}\begin{bmatrix} c^1 \\ \vdots \\ c^r \end{bmatrix} = ec. $$
If $\bar{e}$ is another basis, then since each $\bar{e}_j$ is a vector, there exist coefficients $g_j^i$ such that
$$ \bar{e}_j = e_1g^1_j + \cdots + e_rg^r_j. $$
In other words, $g$ is an invertible matrix such that
$$ \bar{e} = eg. $$
If you have a vector bundle and $e$ and $\bar{e}$ are frames, then the formulas above at each fiber $E_x$ gives you
$$ \bar{e} = eg, $$
where $g$ is now a matrix of scalar functions. This is really a system of $r$ equations of the form
$$ \bar{e}_j = e_1g^1_j + \cdots + e_rg^r_j. $$
If you now take the covariant derivative of each side of this equation, you get by the product rule,
$$ \nabla\bar{e}_j = \nabla e_1 g^1_j + \cdots + \nabla e_r g^r_j + e_1dg^1_j + \cdots e_r dg^r_j. $$
This can be written in matrix form as
$$ \nabla\bar{e} = (\nabla e)g + e(dg). $$
As you have already noted, there is no way to write $g$ directly in terms of $e$ and $\bar{e}$. It exists by the fact that $e$ and $\bar{e}$ are bases of a vector space (at each point in the manifold). As @psl2Z correctly observes, you can write $g$ in terms of $\bar{e}$ and the dual basis of $e$.
$\newcommand\R{\mathbb{R}}$A guick comment about how a frame is equivalent to a trivialization. If you have a frame over $O \subset M$ then there is a diffeomorphism
\begin{align*} \Phi: O\times\R^r &\rightarrow E\\
(x,v) &\mapsto e_1(x)v^1+\cdots+e_r(x)v^r = ev \in E_x.
\end{align*}
The inverse map is a trivialization of $\pi^{-1}(O)$. Given another frame $\bar{e}$, you get another map
\begin{align*} \overline\Phi: O\times\R^r &\rightarrow E\\
(x,v) &\mapsto \bar{e}_1(x)v^1+\cdots+\bar{e}_r(x)v^r = \bar{e}v \in E_x.
\end{align*}
Since
$$ \bar{e}\bar{v} = eg\bar{v}, $$ The transition map between the two trivializations is
\begin{align*}
\Phi^{-1}\circ\overline{\Phi}: O\times\R^r &\rightarrow O\times\R^r\\
(x,\bar{v}) &\mapsto (x,g\bar{v}).
\end{align*}