Deadlocks

I have in a table with some 2000 records with a Document ID which is a Unique Seq Number and details with a Status Flag. Multiple Users access the Table. When a user accesses a particular Document ID the Status flag changes from "N" to "W". Once he finishes working with data on that particular Document ID the Status Changes to "C". When another user tries to pickup a Record the next record in the Seq with the Status as "N" will get fetched. I use a Stored Procedure to assign a Document id to a user and update the Record/status details in the Table. I have used the No lock clause in the SP while retrieving a particular Document ID. It was working fine till sometime. Now it has started giving the following error

Error: Run-time error '-2147467259(80004005)'

[Microsoft][ODBC SQL Server Driver][SQL Server]Your transaction(process ID#127)was deadlocked with another process and as been chosen as the deadlock victim. Return your transaction.

Some one please Help me on how to go abt the problem. Thanks in advance.
Regards
Dinesh1. Run sp_recompile 'object_name' for all objects used.
2. Post it all. SP+DDL

Good luck !