We study taste and Euclidean rotational symmetry violation for staggered fermions at nonzero lattice spacing using staggered chiral perturbation theory. We extend the staggered chiral Lagrangian to O(a^2 p^2), O(a^4) and O(a^2 m), the orders necessary for a full next-to-leading order calculation of pseudo-Goldstone boson masses and decay constants including analytic terms. We then calculate a number of SO(4) taste-breaking quantities, which involve only a small subset of these NLO operators. We predict relationships between SO(4) taste-breaking splittings in masses, pseudoscalar decay constants, and dispersion relations. We also find predictions for a few quantities that are not SO(4) breaking. All these results hold also for theories in which the fourth-root of the fermionic determinant is taken to reduce the number of quark tastes; testing them will therefore provide evidence for or against the validity of this trick.