Automatic grading of test-cases
Have you thought about having a solution that you create and test the students test cases against your solution? Then you have a stable platform for running the student defined tests.

Also run test cases which you prepare against the student's code. Now you have graded the two parts independently of one another.

Just out of curiosity, what did you use for auto-grading?