Start with all the usual debugging stuff:
Make sure all error reporting is on for now:
ini_set('display_errors', true); // set to false for live site
Use some combination of error_log(), echo, print_r(), etc. to check variable/array values.
Check return values from anything that could possibly go wrong (which is basically everything ), and if an unexpected result occurs, generate some debug info.
You can use mysql_affected_rows() to find out how many rows it thinks were deleted. If it comes up with 0, maybe output your query at that point to see what it really tried to do.