Replication problems after server upgrade
Could any operations be altering the values of the primary key columns of the table?

That error can be generated when a replicated update or delete statement cannot find a specific PK value.