My Grid is defined like this

 <asp:GridView runat="server" ID="ProfilesGrid" DataSourceID="ProfilesDataSource"
                            DataKeyNames="PersonID,LetterCode" AllowPaging="True" AllowSorting="True" 
                            OnRowCreated="ProfilesGrid_RowCreated" 
                            OnRowDataBound="ProfilesGrid_RowDataBound"
                            HeaderStyle-CssClass="header_row" RowStyle-CssClass="data_row" SelectedRowStyle-CssClass="selected_row"
                            AutoGenerateColumns="False" OnSelectedIndexChanged="ProfilesGrid_Selected" OnSorting="ProfilesGrid_Sorting"
                            OnSorted="ProfilesGrid_Sorted" PageSize="20" OnRowDeleted="ProfilesGrid_RowDeleted"
                            OnDataBound="ProfilesGrid_DataBound" OnPageIndexChanging="ProfilesGrid_PageIndexChanging">

Does it mean I have to supply LetterCode parameter in my SP?

Yes, looks like it automatically tries to send a second parameter
exec PeopleDelete @PersonID=873,@LetterCode=N'V' if DataKeyNames used. I guess I need to add a parameter.

BTW, I think I tested the delete functionality and it worked OK. I did install SP1 recently.

Adding extra parameter to SP fixed the problem.