Hola,
Tanto nombre como apellido son strings verdad???
En la sentencia intenta ponerlos con comillas asi alomejor te encuentra ese nombre y apellido porque es posible que lo estes comparando mal.
Quedaria algo parecido a esto:
Código PHP:
mysql_query("DELETE FROM usuarios WHERE nombre="."'"."$nombre"."'"." and apellido="."'"."$apellido ");
Cada ."'". son "(dobles comillas) ' (comilla simple) " (dobles comillas) es que se ve muy lioso.