I agree completely. Mara is a good name, but I don't know if it's fitting for the main character. It would be good to incorporate it in using a secondary character as you are suggesting.
I like Mallory the best for this character. Mallory seems like a real person. I don't like it when authors use super plain names (unless it fits the character), but it also also annoys me when they try to make them over-dramatic sounding. Mallory sort of bridges that gap. It's not like Jennifer, but it isn't like Desdemona. (Sorry to all the people who liked that name, but seriously, who in the heck would name their kid that?)
I still vote Anastasia!!!
I say Anastasia too - it's a great name, lots of nickname potential, plus the princess and her sad end. And it's a name that people use in real life. It fits.
:) Finally! (I don't meet...er...see the avatar of (:)) very many people who like Anastasia!