If the depletion layer of a transistor collector/base junction is thick, why are majority carriers still collected?
I thought the collector-base junction was reverse biased which means
  that the electric field created by the external bias adds to the
  potential barrier? How is it that holes spontaneously cross this huge
  potential barrier?


The built-in potential stops the diffusion current due to majority carriers diffusing from one side to the other.  For example, electrons in the N material would diffuse to the P material (where they would recombine) if it weren't for the built-in potential.  For the majority carriers, the built-potential is a barrier.

But in the N material of the base, holes are minority carriers and so, the built-in potential isn't a barrier at all.  If a hole in the base exists long enough, it may be swept across the reverse biased base-collector junction by the electric field there and into the collector region.

When the base-emitter junction is 'on', lots of holes are injected into the thin and lightly doped base region so a large fraction of the injected holes exist long enough to 'slide down' the potential and into the collector region where they are majority carriers.