Why can't I update or delete certain records in SQL Server?
Few Quick Possibilities:


Bad Statistics. Seems unlikely on a table under millions of rows, but technically possible. Try running UPDATE STATISTICS . If this does work look into why your statistics are getting out of whack and what you can do to mitigate the problem.
Lack of a good Clustered Index. This can be related to #1, if your CI is bad it can slow down UPDATEs/DELETEs as the CI needs to be searched and adjusted during such changes, but an INSERT may just be adding to the end of the CI.
Locks are being held too long over some sections of the table via other processes. Other transactions may be holding a lock on the table for excessive amounts of time, this may also be visible as deadlocking if you have the appropriate flags turned on for the SQL Logs.


Manually grabbing the query plan and taking a look at that may also help you figure out what is going on.