It's been officially confirmed that the Franklin predates Archer's Enterprise, see this article:
And if you think this is just our speculation, worry not: we got a note from Dylan Highsmith, one of the lead picture editors on STAR TREK BEYOND, about this very issue.
If you want the official explanation on the Franklin and it’s warp factor: it was a M.A.C.O. ship (or a United Earth Starfleet ship that housed M.A.C.O. personnel at times) that predates the NX-01.
When the UFP Starfleet is formed, M.A.C.O. was disbanded and the ship was reclassified as a Starfleet ship [with the USS identifier]. The ship is then “lost” in the early 2160’s.
It was important to everyone that the ship, like Edison, predate the Federation; that thematically, the ship mirrored an earlier time in history and served as a bridge in design between then and the NX-01.
Doug [Jung] and Simon [Pegg] may have worked up something [on an official launch date], but if they did it never made it to script or screen.
Either way it predates the NX-01, and was reclassified after the UFP is formed.
If it was built as a M.A.C.O. ship rather than a Starfleet ship that could explain the seeming inconsistency in registry order, though Dylan Highsmith also speculates it could have been a "United Earth Starfleet ship that housed M.A.C.O. personnel at times," which would still leave us with the same problem. But in that case, this reddit thread gives a good argument involving the German tank problem for why Starfleet might choose to assign registry numbers non-sequentially--basically, if vehicles (or components inside vehicles) are numbered sequentially, then a random sample can allow an enemy to estimate total numbers, and the "countermeasures" section of the article notes one solution is non-sequential registries:
serial numbers that resist cryptanalysis can be used, most effectively by randomly choosing numbers without replacement from a list that is much larger than the number of objects produced
The answer by @Ashley Darkstone also notes in option #2 that the timeline may have been retroactively changed, so maybe in this timeline Archer's Enterprise wasn't the NX-01. This is definitely a possibility, but one caution I would note about this idea is that Pegg seemingly only proposed this idea to defuse controversy about making Sulu gay, so my guess was this wasn't the operating conception of the writers when the movie was actually written. Furthermore, Pegg's proposal seems to be based on a misconception--he thought Sulu was born before 2233 when Nero arrived and the Kelvin incident occurred, but actually the best available info suggests Sulu was born after 2233 (probably in 2237), and Pegg probably got this idea from some badly-sourced info in an older edit of Sulu's wikipedia article, see my comment here for details.
