You need to check it is moving FULLY, the solenoid pulls on a little linkage that rotates a circular piece of metal at the end of the lock barell, if it cannot move fully(partially seized) this will give what you have, just take lock out and it is easy to see how it works,.
As the circular piece moves(rotates) it ligns up a CUTOUT section of it which allows ther pluger(lock button) to be depressed.
tabetha