Recent studies have shown that distant red galaxies (DRGs), which dominate the high-mass end of the galaxy population at z~2.5, are more strongly clustered than the population of blue star-forming galaxies at similar redshifts. However these studies have been severely hampered by the small sizes of fields having deep near-infrared imaging. Here we use the large UKIDSS Ultra Deep Survey to study the clustering of DRGs. The size and depth of this survey allows for an unprecedented measurement of the angular clustering of DRGs at 2<z_phot<3 and K<21. The correlation function shows the expected power law behavior, but with an apparent upturn at theta<~10. We deproject the angular clustering to infer the spatial correlation length, finding 10.6+-1.6 h^-1 Mpc. We use the halo occupation distribution framework to demonstrate that the observed strong clustering of DRGs is not consistent with standard models of galaxy clustering, confirming previous suggestions that were based on smaller samples. Inaccurate photometric redshifts could artificially enhance the observed clustering, however significant systematic redshift errors would be required to bring the measurements into agreement with the models. Another possibility is that the underlying assumption that galaxies interact with their large-scale environment only through halo mass is not valid, and that other factors drive the evolution of the oldest, most massive galaxies at z~2.