Mysql – thesql replication stop/start causes duplicate rows

Double check that your character sets on the databases and connections are what you expect them to be - your replication choking on a statement with a non-ASCII character is immediately suspicious.

Look at the master's binary log to see how the statement it logged is different from the statement that the replica is trying to execute - that will offer clues to the problem.

Sadly, you should also make sure that the versions of the server for both the master and slave are the same. I recently encountered a weird instance where we had bad SQL trying to update a non-NULL numeric column to NULL. In the version that the master was running, MySQL silently converted it to 0, but in the version that the replica was running, it was an error.

Also, instead of doing CHANGE MASTER to fix the replica, you should be doing

STOP SLAVE;
[correct and execute whatever statement is the problem]
SET GLOBAL sql_slave_skip_counter = 1;
START SLAVE;

http://dev.mysql.com/doc/refman/5.1/en/set-global-sql-slave-skip-counter.html

Is it the InnoDB storage engine?

This error means that MySQL doesn't have enough room to store all of the rows lock that it would need to execute your query. Depend on RAM you have, set innodb_buffer_pool_size to a reasonable value (256MB, 512MB), you will probably never encounter this error.

Check the default value with mysql> show global variables like 'innodb_buffer%';.