Sql-server – unique key violation occuring on a unique value combination

SQL SERVER 2008
I have a mapping table that contains a deleted date column. Since the table uses a surrogate key as its unique identifier there is a uniqueness constraint on the table. This constraint contains each of the foreign key values and the deleted date.

I have a process that runs each night and attmepts to modify this data based on an external data source. The process is attempting to update a record and set its deleted date to GETDATE(). There is currently a record in the mapping table witht he same foreign key values and a deleted date of 2011-12-17 00:17:22.157. The process is returning the following error

Violation of UNIQUE KEY constraint 'UNQ_tsitemapping_fullcolumnlist'. Cannot insert duplicate key in object 'dbo.tSiteMapping'. The duplicate key value is (4, , 5, , 1394, 154, Dec 21 2011 6:59AM).

Shouldnt the inclusion of the deleted date in the uniqueness constraint mean that this is a unique value? Why would I be getting a UNIQUE KEY constraint violation on this table?
Any suggestions on how to fix this problem would be welcome.

As Per GBN's comment below. Here is the table definition.

SET ANSI_NULLS ON
GO

SET QUOTED_IDENTIFIER ON
GO

CREATE TABLE [dbo].[tSiteMapping](
    [intSiteMappingID] [int] IDENTITY(1,1) NOT NULL,
    [intEntityID] [int] NOT NULL,
    [intParentCompanyID] [int] NULL,
    [intMarketSegmentID] [int] NULL,
    [intRegionID] [int] NULL,
    [intSiteID] [int] NOT NULL,
    [dtEntered] [datetime] NOT NULL,
    [dtModified] [datetime] NULL,
    [dtDeleted] [datetime] NULL,
    [intdivisionid] [int] NULL,
 CONSTRAINT [PK_lSiteMapping] PRIMARY KEY CLUSTERED 
(
    [intSiteMappingID] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY],
 CONSTRAINT [UNQ_tsitemapping_fullcolumnlist] UNIQUE NONCLUSTERED 
(
    [intEntityID] ASC,
    [intParentCompanyID] ASC,
    [intMarketSegmentID] ASC,
    [intRegionID] ASC,
    [intSiteID] ASC,
    [intdivisionid] ASC,
    [dtDeleted] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

GO

ALTER TABLE [dbo].[tSiteMapping]  WITH CHECK ADD  CONSTRAINT [FK_tSiteMapping_lEntity] FOREIGN KEY([intEntityID])
REFERENCES [dbo].[lEntity] ([intEntityID])
GO

ALTER TABLE [dbo].[tSiteMapping] CHECK CONSTRAINT [FK_tSiteMapping_lEntity]
GO

ALTER TABLE [dbo].[tSiteMapping]  WITH CHECK ADD  CONSTRAINT [FK_tSiteMapping_tSite] FOREIGN KEY([intSiteID])
REFERENCES [dbo].[tSite] ([intSiteID])
GO

ALTER TABLE [dbo].[tSiteMapping] CHECK CONSTRAINT [FK_tSiteMapping_tSite]
GO

ALTER TABLE [dbo].[tSiteMapping] ADD  CONSTRAINT [DF_lSiteMapping_dtEntered]  DEFAULT (getdate()) FOR [dtEntered]
GO

The following query is the query that is failing

UPDATE tSiteMapping
   SET dtDeleted = GETDATE()
 WHERE NOT EXISTS (SELECT 1
                     FROM crm...qapps a
                          JOIN crm...parent_company pc ON pc.id = a.intparentcompanyid
                          LEFT OUTER JOIN tSite s ON s.intAppID = a.appid AND s.dtDeleted IS NULL
                          LEFT OUTER JOIN lEntity e ON e.strEntity = a.enterprise_name AND e.dtDeleted IS NULL
                          LEFT OUTER JOIN lParentCompany lpc ON lpc.strParentCompany = CASE 
                                                                                           WHEN SUBSTRING(pc.companyname, 0, CHARINDEX(' - ', pc.companyname, 0)) LIKE '%Canada%' THEN
                                                                                                REPLACE(SUBSTRING(pc.companyname, 0, CHARINDEX(' - ', pc.companyname, 0)), 'Canada', 'CAN')
                                                                                           WHEN SUBSTRING(pc.companyname, 0, CHARINDEX(' - ', pc.companyname, 0)) LIKE '%  USA%' THEN
                                                                                                REPLACE(SUBSTRING(pc.companyname, 0, CHARINDEX(' - ', pc.companyname, 0)), '  USA', ' USA')
                                                                                           ELSE SUBSTRING(pc.companyname, 0, CHARINDEX(' - ', pc.companyname, 0))
                                                                                       END AND lpc.dtDeleted IS NULL
                          LEFT OUTER JOIN lDivision d ON d.strDivision = SUBSTRING(pc.companyname, CHARINDEX(' - ', pc.companyname, 0)+3, LEN(pc.companyname) - (CHARINDEX(' - ', pc.companyname, 0)+3)+1) AND d.dtDeleted IS NULL
                          LEFT OUTER JOIN lMarketSegment ms ON ms.strMarketSegment = a.strsitecategory AND ms.dtDeleted IS NULL
                          LEFT OUTER JOIN lRegion r ON r.strRegion = CASE 
                                                                         WHEN a.region = 'New England' THEN
                                                                              'North East'
                                                                         WHEN a.region = 'Northeast' THEN
                                                                              'North East'
                                                                         ELSE a.region
                                                                     END AND r.dtDeleted IS NULL
                    WHERE a.appname != ''
                      AND a.appname IS NOT NULL  
                      AND a.[server] != ''
                      AND a.[server] IS NOT NULL
                      AND a.[server] != 'CTXT'
                      AND CONVERT(VARCHAR(4000),a.appurl) != ''
                      AND a.appurl IS NOT NULL 
                      AND tSiteMapping.intSiteID = s.intSiteID
                      AND isnull(tSiteMapping.intEntityID, 0) = isnull(e.intEntityID, 0)
                      AND isnull(tSiteMapping.intParentCompanyID, 0) = isnull(lpc.intParentCompanyID, 0)
                      AND isnull(tSiteMapping.intMarketSegmentID, 0) = isnull(ms.intMarketSegmentID, 0)
                      AND isnull(tSiteMapping.intRegionID, 0) = isnull(r.intRegionID, 0)
                      AND isnull(tSiteMapping.intdivisionid, 0) = isnull(d.intdivisionid, 0)
                      AND tSiteMapping.dtDeleted IS NULL)

Here are the rows in the table that have the conflict

intSiteMappingID, intEntityID, intParentCompanyID, intMarketSegmentID, intRegionID, intSiteID, dtEntered, dtModified, dtDeleted, intdivisionid

12816, 4, NULL, 5, NULL, 1394, 2011-12-17 00:17:24.283, NULL, NULL, 154

12512, 4, NULL, 5, NULL, 1394, 2011-12-16 09:32:41.100, NULL, 2011-12-17 00:17:22.157, 154

The update should be updating the record with the NUll dtdeleted date and setting it to GETDATE() which appears to be throwing the error.