We provide an analytic theory of Anderson localization on a lattice with a weak short-range correlated disordered potential. Contrary to the general belief, we demonstrate that already next-neighbor statistical correlations in the potential can give rise to strong anomalies in the localization length and the density of states, and to the complete violation of single-parameter scaling. Such anomalies originate in additional symmetries of the lattice model in the limit of weak disorder. The results of numerical simulations are in full agreement with our theory, with no adjustable parameters.