There is an issue with "proposed" and "solved". Of all the examples the Archimedes Cattle Problem is the only one that was truly proposed and solved. The oracle of Delphi allegedly "proposed" duplication to the Athenians, but it could not have been very precise since they originally took it to mean doubling the sides. Who proposed quadrature and trisection is hidden in the mists of time (in a practical context finding the area of a circle already appears as problem 50 in the Rhind papyrus c. 1600 BC), but they apparently did not specify that it had to be done with straightedge and compass either, because all three were solved within a hundred years of being "proposed" by other means (e.g. quadrature was solved by Dinostratus c. 350 BC, using quadratrix). And one has to be really precise, because already Archimedes knew how to solve duplication and trisection with marked straightedge and compass.
That with such precise restrictions there were no solutions was suspected in late antiquity, as follows from Pappus's classification of problems into plane (solved with straightedge and compass), solid (solved with conic sections), and other, but the idea of proving something like that does not emerge as a problem until 17th century, when Gregory attempted proving the impossibility of quadrature in 1667. So what was "solved" in 1837 and 1882 is not what was "proposed" in 5th century BC.
Similarly, Euclid did not "propose" to derive the parallel postulate from other postulates, although many took his verbose phrasing and avoiding the use of it for half of book I as an invitation to do so. Fermat did not propose the Last Theorem as a problem either, he stated it, and mentioned on the margins of his copy of Diophantus's Arithmetica that he "discovered a truly marvelous proof of this, which this margin is too narrow to contain". Only later Euler and others realized that something was amiss when they tried to reproduce this "marvelous proof". It is more accurate to say that all these problems, as we know them today, emerged over time from multiple people playing with a common theme.
But this is Guinness Book of Records, so we shouldn't be too picky. In which case Pythagoreans already cared about perfect numbers in 6th century BC, Euclid gives a familiar characterization of them in Elements IX.36 (c.300 BC). They probably wondered if there is the largest among them, Euclid answers such question about primes in Elements IX.20, Nichomachus implied the same answer for perfects c. 100 AD. In any case this is what emerged after centuries of playing with them, so the problem "originates" before all of the above, and it is still open.