Why should I avoid the Frobenius Norm?

The Frobenius norm is actually quite nice, and also natural. it is defined by merely $$\|A\|_F^2 = \mbox{trace}(A'A)$$

and since it is naturally an inner-product norm, it makes optimization, etc. with it much easier (think quadratic programs, instead of semidefinite programs)

Numerical analysis probably like the operator norm perhaps because they often exploit $\|Ax\| \le \|A\| \|x\|$, and if you use the operator-2 norm, you get a tighter inequality (in general).

Otherwise, what norm you use, should be governed by the application where you are trying to use it.

As Joel Tropp puts it:

Frobenius norm error bounds are typically vacuous.

"An Introduction to Matrix Concentration Inequalities," (arxiv), page 84

The reason is explained there, and also in the Appendix of this paper. Essentially, noise shows up as a long tail of singular values that are individually much smaller than the leading singular value, but when summed up, may exceed the leading singular value. The Frobenius norm is the sum of squares of the singular values, and hence, you are just measuring noise--the signal has little effect. The spectral norm, on the other hand, is just the leading singular value--and hence it is measuring the actual signal.