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.