I presume by lock you mean prevent further editing? You can do this with a validation rule. So (pl__c is the api name of your picklist)
ISPICKVAL(pl__c,"New") && ISCHANGED(graded__c) would be it if I understand correctly.
I've just checked in a sandbox here ISCHANGED does work with a checkbox field.
(Should have done this as a answer not a comment - which I've deleted)
This is a working example based on Opportunity.Type and Opportunity.Stage. You can use
ISCHANGED() with a picklist:
Thinking about this you may also potentially want to look at using field dependencies, but this wouldn't be true security - it would only be enforced in the UI and not in any API interactions: