OK – it looks as though (in my case at least) the answer was to set all non primary-key column’s UpdateCheck property to Never in the DBML file. Doing this immediately cured the problem of “Row not found or changed”.
Given the rumour that Microsoft are moth-balling Linq-To-Sql in favor of Entity Framework, one wonders whether these sorts of bugs will be fixed?