In the original exercise, there is an additional assumption (that cannot be dispensed with, as Byron Schmuland has shown):
We also assume the $A_n$ exhibit one of two modes of behaviour: either the $A_n$ converge to zero, or else they are bounded away from zero (i.e. there exists $c>0$ such that $A_n\geq c$ for every $n$. It is easy to see that if a sequence does not converge to zero, then it has a subsequence that is bounded away from zero, so it does not cause too much loss of generality to restrict to one of these two cases.
The proof now becomes rather simple. It is very easy to see that $A_n\to 0$ or $\mu(E_N^*)\to 0$ are sufficient for almost uniform convergence to zero.
For the other direction, assume that $A_n$ does not converge to $0$, but $f_n$ converges almost uniformly to $0$. Let $\epsilon>0$. There is a $F$ with $\mu F<\epsilon$ such that $f_n$ converges uniformly to zero outside $F$.
In particular there exists $N$, such that outside $F$, we have $f_n< c$ for $n\geq N$. But $c 1_{E_n}(x)\leq A_n 1_{E_n}(x)< c$ implies $1_{E_n}(x)=0$, hence $E_n\subseteq F$ for all $n\geq N$. This implies that $\bigcup_{n\geq N} E_n=E_N^*\subseteq F$, and hence $\mu(E_N^*)\leq\mu(F)<\epsilon$. Since the $E_N^*$ are a decreasing sequence, this shows that $\mu(E_N^*)\to 0$.