Complexity of n-queens-completion?
It's taken years but this post inspired us to write a paper which has come out today.  

The answer is that n Queens Completion is NP-Complete.  However for full disclosure should mention we solve a slight variant of the problem.  In our case the set of queens doesn't have to be a prefix of the full set.  So technically we haven't resolved the exact problem asked here.  However it would be extremely surprising if the version of n Queens Completion from this query wasn't also NP-Complete.

I want to repeat the thanks we put in the paper to Jeffε for raising this question here.  

The complexity of n Queens Completion
Journal of AI Research
Gent, Jefferson, Nightingale
doi:10.1613/jair.5512 
http://www.jair.org/papers/paper5512.html