I would do a 10046 trace so to be sure what the statement is actually doing.

Couple of questions...
1- How many rows out of the total number of rows on the table is supposed to delete the statement?
2- I assume there is an index on the column_name used on the predicate of the delete statement - if this is the case, are table and index statistics up to date?

Hope this helps.