We present a detailed statistical analysis of the correlation between radio and gamma-ray emission of the Active Galactic Nuclei (AGN) detected by Fermi during its first year of operation, with the largest datasets ever used for this purpose. We use both archival interferometric 8.4 GHz data (from the VLA and ATCA, for the full sample of 599 sources) and concurrent single-dish 15 GHz measurements from the Owens Valley Radio Observatory (OVRO, for a sub sample of 199 objects). Our unprecedentedly large sample permits us to assess with high accuracy the statistical significance of the correlation, using a surrogate-data method designed to simultaneously account for common-distance bias and the effect of a limited dynamical range in the observed quantities. We find that the statistical significance of a positive correlation between the cm radio and the broad band (E>100 MeV) gamma-ray energy flux is very high for the whole AGN sample, with a probability <1e-7 for the correlation appearing by chance. Using the OVRO data, we find that concurrent data improve the significance of the correlation from 1.6e-6 to 9.0e-8. Our large sample size allows us to study the dependence of correlation strength and significance on specific source types and gamma-ray energy band. We find that the correlation is very significant (chance probability <1e-7) for both FSRQs and BL Lacs separately; a dependence of the correlation strength on the considered gamma-ray energy band is also present, but additional data will be necessary to constrain its significance.Read less <