error al borrar un registro enuna tabla relacionada

hola:
Tengo problemas al borrar (desde web developer, c#) un registro en una tabla
almacenada en SQL Server 2005
Tengo 3 tablas relacionadas y con los siguientes campos:

Empleados (IdEmpleado(PK),.)
EmpeadosVehiculos (IdEmpleado,IdVehiculo,FechaInicio,FechaFin), donde
IdEmpleado,IdVehiculo,FechaInicio(PK)
IdEmpleado,FechaInicio(IX), son clave única para que en una fecha 1 empleado
sólo tenga un
vehículo.
IdVehiculo,FechaInicio(IX), son clave única para que en una fecha 1 vehículo
sólo pueda
estar en 1 empleado.
Vehiculos (IdVehiculo(PK),..)

Un empleado sólo puede tener asignado un vehículo y un vehículo sólo puede
estar en un empleado (para una fecha determinada).
el caso es que al BORRAR 1 vehículo:
* compruebo que para esa fecha no esté asignado, que no aparezca en
EmpleadosVehiculos para esa fecha, hasta ahí todo bien, pero cuando va a
borrar, lanza la siguiente excepcion:
Instrucción DELETE en conflicto con la restricción
REFERENCE "FK_Empleados_Vehiculos_Vehiculos".
El conflicto ha aparecido en la base de datos "recursos",
tabla "dbo.Empleados_Vehiculos",
column 'idVehiculo'
En la relación "FK_Empleados_Vehiculos_Vehiculos", tengo:
Tabla de clave Principal: Vehiculos (IdVehiculo)
Tabla de clave Externa:EmpleadosVehiculos (idVehiculo)

Si alguien me puede ayudar, yo creo que las relaciones están bien, pero algo
falla.
Un saludo.