We report on a two-loop supersymmetric contribution to the magnetic moment (g-2)_mu of the muon which is enhanced by two powers of tan(beta). This contribution arises from a shift in the relation between the muon mass and Yukawa coupling and can increase the supersymmetric contribution to (g-2)_mu sizably. As a result, if the currently observed 3 sigma deviation between the experimental and SM theory value of (g-2)_mu is analyzed within the Minimal Supersymmetric Standard Model (MSSM), the derived constraints on the parameter space are modified significantly: If (g-2)_mu is used to determine tan(beta) as a function of the other MSSM parameters, our corrections decrease tan(beta) by roughly 10%
for tan(beta)=50.