So he could have been saying:
During the era of this kingdom, all people (humans + mystics) could use magic.
Afterwards, humans could no longer use magic, but the mystics still could.
This is an interesting comment, and it makes me think that perhaps Spekkio has a broader definition of 'people' than we generally assume. The Mystics in Medina are obviously 'people' in that they are intelligent civilized beings, yet most of the characters in the game do not consider them people, at least when referencing them, due to their past behavior as dangerous monstrous beings during the war. This is at least partly just to identify that the NPCs aren't talking about dangerous humans, but specifically the mystics... however, it also makes it appear that the human view of 'people' only applies to human beings.
Back to the subject of 'where did they come from,' I think its possible that they are the intelligent evolution of existing creatures, even going as far back as Zeal, they may have been intelligent. Most enemies fail to address the player before a fight, so if we assume they
can't simply because they don't, then the majority of existing mystics in the game are quite feral. Mt. Woe (I believe) contains Feral Imps and Imp Aces (as I recall). They already seemed to be domesticating animals to do their work, which to me implies that they are at least somewhat intelligent by this point.
I think it's reasonable that in the 64,988,000 years between Ioka and Zeal, the creatures of the world (Though not all) may have become intelligent. I also believe that the mystics are not a race of people at all, but rather many races of people, each coming from a different evolutionary lineage, and each, throughout the years, being shunned, hunted, assaulted by humans, to the point where they eventually became a united front against them.
Lavos' goal is to collect DNA with advanced or useful properties... I think it's possible that it could thus influence the development of lesser creatures to become intelligent and eventually be yet more fodder for harvest.
I suppose in a timeline my thoughts flow this way:
65m BC: No mystics, primitive animal life, Lavos arrives. Lavos sees not enough potential in humans alone for cultivation, and reptites are dying out due to Lavos' arrival.
65m BC: Lavos begins seeding the DNA of multiple creatures in a symbiotic plan to advance them, so it can be advanced using them.
65m-12k BC: Multiple life forms begin using tools, communicating, becoming intelligent... how fast this happens is unknown, nor is the level of this intelligence at any point known. It may be that 'mystic-like' intelligent life started appearing only months after Lavos came... or it could be millennia or eons... Humanity, in possession of the Red Stone (generic, not a singular stone), continues to advance at an accelerated rate.
12k BC: Humanity is highly advanced, with thanks to the Red Stone and likely the Flame. Mystic-like intelligent beings exist, but may not be as intelligent as the land dwelling humans, or may be moreso, no information is available.
12k BC: Zeal falls. Humanity is set back, but continues to advance, now in unison. Mystic-like beings may take control of any Zeal remains, thus becoming exposed to magic if they had not already been.
...
600-1000 AD: Mystics are the current end-point of the developing intelligent beings thusfar.
1999 AD: Mystics are nearly if not entirely obliterated by Lavos, along with most of humanity.
2300 AD: Surviving mystics, if there are any, are few and have possibly mutated, losing the ability for magic, or with other effects. Krawlie may be a mystic-descendant, as may the 'fish-men.'
Theory on Mystic's magical ability:
Nu. Nu are prevalent in Zeal, and once Zeal falls, we see that some Zealeans survive, so it's possible many Nu do as well. Nu being a part of Zeal's magical culture, may be the influence on the mystic-like beings that eventually allows them to learn magic.