I have a character with 8 missions and 6 kills, and still she is a rookie. Some seem to get promoted, while others get sent on missions, make kills, and yet stay as rookies. Is this a bug, or is there something else controlling how soldiers get promoted? I am playing on Classic difficulty.
That sounds like a bug. One kill is good for the first promotion. I have never read anything that suggested soldier advancement was slower on Classic.