As I understood after googling as well cognomina were not used by *normal* people until around 100 BCE.
Here is a list of
Roman senators that show the first senator with the cognomen Priscus already in the 5th century BC:
http://en.wikipedia.org/wiki/List_of_Republican_Roman_Consuls
And here is an interesting article about
Roman naming practices that says essentially the same regarding the first occurence of Priscus:
http://www.sca.org/heraldry/laurel/names/roman/index.html
But regarding the point in time when the female form of the cognomen was first used as a given name: No luck...
Rene www.AboutNames.ch