The time barrier was a theoretical barrier in the development of mid-23rd century warp drive. This obstacle was overcome sometime between 2236 and 2254 (between the time of the crash-landing of the SS Columbia on Talos IV and the arrival of the USS Enterprise, allowing Federation star ships to travel significantly faster than ever before. (TOS: "The Cage")
For many years, Starfleet, like many other peoples of the Alpha & Beta quadrant, tried to reach warp 8, but were limited at warp 7.3, by some kind of speed "barrier". One hypothesis about this "barrier" was that there was a "desynchronization of time" in the subspace field around the bubble that surrounds the ship at speeds above warp 7. This problem was called the temporal barrier or "Time barrier".
This problem was discovered around 2200 when new ships tried to reach warp 8 and only reached a maximum speed of warp 7.3 due to subspace field instability problems at these speeds. Over the next 35 years, the UFP was unable to reach a speed of more than warp 7.3.
To reach warp 8, the UFP designed a new warp core and warp coils from scratch (the Klingons built a Warp 8 core before the UFP, based on reverse engineering of captured Hydran ships, but there were flaws in the design of these coils, which kept it from truly breaking the barrier; so the Warp 7.3 barrier was still unbeaten, except for some older warp races, like the Hydrans). The new warp core of the UFP generated more output of energy than the Klingon Warp 8 core. Also, the Federation was in the final stages of testing it in 2235 with two ships of Arizona class. At the same time, the Federation was testing a new design of warp coils in the first ships of the Legend class.
The Legends class was designed, originally, to be mainly a deep space explorer and break the "Time barrier" with its new warp coil designs and new warp reactor.
Barrier or bad math?Edit
Fundamentally, the "temporal barrier" was a false barrier. It came from a bad understanding of warp field equations. It was eventually discovered that the original equations of Zefram Cochrane were only 75% of the real equation. This error was discovered in the late mid-23rd century. One of the engineers who discovered this problem was Montgomery Scott, the Chief Engineer of USS Enterprise. He used his own equations based on this error to show that the "Trans Warp drive" of the Excelsior must fail. His notes on deep warp field studies also helped in the developement of the new warp scale around the last years of the 23rd century.