Some people have been experiencing the following error message in the event log:

Event Type: Error
Event Source: MSCRMDeletionService
Event Category: None
Event ID: 16387
Date: Date
Time: Time
AM User: N/A
Computer: Computer_Name
Description:
Error: Deletion Service failed to clean up some tables.

Microsoft has a solution for this message. See http://support.microsoft.com/kb/921391/EN-US/ for their solution.

Personally I don't feel comfortable with the solution they give. They are removing the enforced relationships for the tables which cause the issue. This will leave you with orphaned records in your database and probably the same issue when you upgrade to the upcoming titan release. Here are my steps to correctly fix this issue (partly copied from the MS solution) :

To identify the table where the Deletion Service is failing, follow these steps:
1. On the Microsoft Dynamics CRM server, click Start, click Run, type cmd, and then click OK.
2. At the command prompt, locate the system drive, locate the program files, locate Microsoft Dynamics CRM, locate the server, locate the bin, type crmdeletionservice.exe –runonce, and then press ENTER. You then receive a message that resembles the following message:
Can't clean up the following tables: Campaign

Note The table that is returned in the message is the table for which the Deletion Service failed.

The following example demonstrates how to resolve this problem for the Campaign table.

To resolve the problem for the Campaign table, follow these steps:
1. Run a statement in Microsoft SQL Query Analyzer. To do this, follow these steps:
a. Click Start, point to All Programs, point to Microsoft SQL Server, and then click Query Analyzer.
b. Run the following query against the Organization Name_MSCRM database.
delete from Campaign where DeletionStateCode = 2
This query returns a message that resembles the following message:

DELETE statement conflicted with COLUMN REFERENCE constraint 'campaign_leads'.

2. Run two queries agains the Organization Name_MSCRM database.
delete from [table name in message] where [column name in message] in (select campaignid from Campaign where DeletionStateCode = 2)

delete from Campaign where DeletionStateCode = 2

By doing this, you do delete the associated records as well. Keep in mind that once deleted, you cannot get the data back. Therefore always make a backup first!