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.