This might be considered as cheating"cheating" (since this does not change your code), but nobody mentioned using Pypy. You are using pure python and your program runs perfectly with Pypy.
For a 10x10 board (as suggested by @vnp, I moved the timing so keys pressing are not timed):
pypy nqueens.py ('\n Total number of solution is: ', 724) --- Time: 0.224999904633 seconds --- python nqueens.py ('\n Total number of solution is: ', 724) --- Time: 1.37299990654 seconds ---