This is just guesswork but as far as I can tell...
Momiji wrote:but seriously, can we get some (more) accurate information on the requirements of titles? i-i really want a new title
You start by determining your highest stat, e.g. Accuracy at 614, then calculate ~80% of that == 491.2 and your title is determined by whichever stats are at 491.2 or higher, e.g. Accuracy, Stamina and Tenacity, giving you fearless.
So since your accuracy increased to 625, the requirement changed to 500,. Since your Agility went from 485 (below the threashold) to 515 (above it), you went from Fearless to Versatile.