Supponendo di avere le due nuove date nelle variabili $data1 e $data2, potresti fare una select di questo tipo:
Codice PHP:
$query = "SELECT * FROM tabella WHERE id='Mario' AND (" . $data1 . " >= data1 AND " . $data1 <= " . $data2) OR (" . $data2 . " >= data1 AND " . $data2 <= " . $data2)"; 
Se la query trova qualcosa allora Mario è già occupato nel nuovo intervallo di tempo.