We present new results on the cosmological evolution of the near-infrared galaxy luminosity function, derived from the analysis of a new sample of ~22,000 K(AB) < 22.5 galaxies selected over an area of 0.6 square degrees from the Early Data Release of the UKIDSS Ultra Deep Survey (UDS). Our study has exploited the multi-wavelength coverage of the UDS field provided by the new UKIDSS WFCAM K and J-band imaging, the Subaru/XMM-Newton Deep Survey and the Spitzer-SWIRE Survey. The unique combination of large area and depth provided by this new survey minimises the complicating effect of cosmic variance and has allowed us, for the first time, to trace the evolution of the brightest sources out to z~2 with good statistical accuracy. In agreement with previous studies we find that the characteristic luminosity of the near-infrared luminosity function brightens by 1 magnitude between z=0 and z~2, while the total density decreases by a factor ~2. Using the rest-frame (U-B) colour to split the sample into red and blue galaxies, we confirm the classic luminosity-dependent colour bimodality at z<1. However, the strength of the colour bimodality is found to be a decreasing function of redshift, and seems to disappear by z>1.5. Due to the large size of our sample we are able to investigate the differing cosmological evolution of the red and blue galaxy populations. It is found that the space density of the brightest red galaxies (M_K < -23) stays approximately constant with redshift, and that these sources dominate the bright-end of the luminosity function at redshifts z<1. In contrast, the brightening of the characteristic luminosity and mild decrease in space density displayed by the blue galaxy population leads them to dominate the bright-end of the luminosity function at redshifts z>1.