We have analysed a sample of 25 extremely red H-[4.5]>4 galaxies, selected using 4.5 micron data from the Spitzer SEDS survey and deep H-band data from the Hubble Space Telescope (HST) CANDELS survey, over ~180 square arcmin of the UKIDSS Ultra Deep Survey (UDS) field. Our aim is to investigate the nature of this rare population of mid-infrared (mid-IR) sources that display such extreme near-to-mid-IR colours. Using up to 17-band photometry (U through 8.0 microns), we have studied in detail their spectral energy distributions, including possible degeneracies in the photometric redshift/internal extinction (zphot-Av) plane. Our sample appears to include sources of very different nature. Between 45% and 75% of them are dust-obscured, massive galaxies at 3300 microJy, which at 35) sources at zphot<1. Finally, we analyse in detail two zphot~6 galaxy candidates, and discuss their plausibility and implications. Overall, our red galaxy sample contains the tip of the iceberg of a larger population of z>3 galaxies to be discovered with the future James Webb Space Telescope.