Tu codigo elimina cita por cita, eso quiere decir que el do se esta ejecutando el numero de veces que registros tienes en tu tabla, prueba sacar el boton del do while, eso debe arreglar el problema, yo lo haria asi:
<table>
<tr>
</tr>
<tr>
<td height="134" colspan="2">
<div class="Estilo2">
<?php if ($totalRows_citas == 0) {
echo 'No hay citas registradas para este día';
} else {?></div>
<table width="1050" border="1" align="center">
<tr class="Estilo2">
<td align="center" width="120">Doctor</td>
<td align="center" width="120">Paciente</td>
<td align="center" width="80">Fecha </td>
<td align="center" width="60">Hora</td>
<td align="center" width="167">Observaciones</td>
<td align="center" width="80">Opciones</td>
</tr>
<?php do { ?>
//Y aqui voy llenando mi tabla con los registros
<tr class="Estilo3">
<td><?php echo $row_citas['doctor']; ?></td>
<td><?php echo $row_citas['paciente']; ?></td>
<td align="center"><?php echo $row_citas['fecha_cita']; ?></td>
<td align="center"><?php echo $row_citas['hora']; ?></td>
<td><?php if ($row_citas['observaciones'] != '')
echo $row_citas['observaciones'];
else
echo " - - - "; ?></td>
<td align="center">
<table width="73" border="0">
<tr>
<td align="center" ><a href="Cita-Modificacion.php?recordID=<?php echo $row_citas['cvecita']; ?>"><img src="imagenes/lapiz.JPG" width="21" height="22" border="0" alt="Editar"></a></td>
<td align="center" ><a href="Cita-Detalles.php?recordID=<?php echo $row_citas['cvecita']; ?>"><img src="imagenes/detalles.JPG" width="22" height="22" alt="Detalles" border="0">
<?php } while ($row_citas = mysql_fetch_assoc($cita)); ?>
</a></td>
</tr>
</table>
</tr>
<!-- Aqui es donde deseo que al momento de hacer click, el usuario pueda eliminarse el registro-->
<td align="center" ><img src="imagenes/cancelar.JPG" width="16" height="16" alt="Detalles" border="0" onClick="<?php ElimCita($row_citas['cvecita']); ?>"></td>
</tr>
</table>
Prueba sacando el boton de el do while, pon el boton fuera del ciclo.