I read this book in 2009, when I randomly stumbled upon it on a shelf. The book started by talking about something along the lines of "gatekeepers", but the concept was completely irrelevant until the very end of the book.
The main story was about a girl that was the daughter of a noble and a prostitute. As the mother lay dying, the nobleman took the girl into his household. The girl then grew attached to the male heir of the house.
I remembered something about how the lady of the house realizes that the girl is actually the daughter of the nobleman, so she separate the two by sending the male heir to marry into some other tribe.
Further along the story, the girl's power was awoken. She seems to control fire. If I remember correctly, this book is one of the few books in the series. The book that came after this one had "Earth" or "Stone" in it, so I am assuming all the books in this series are named after the elements. Please help if you can inform me of the book title