My first suggestion, would be to dump the "flag" variable, and change the methods so they return true if the test is "ok", then short circut out if any of the tests fail...

for ($candidate = 12345;
     $candidate <= 98765;
     $candidate++) {
       if (check_prime($candidate) &&
           check_digit_3($candidate) &&
           check_digit_2($candidate) &&
           check_digit_5($candidate) &&
           #check_duplicates($candidate) && # problem?
           check_digit_1($candidate)) {
         print "$candidate\n";
       }
}
[download]

...so you don't waste time on tests that don't matter (because you allready know other tests don't work).