Mysql: Deadlock found when trying to get lock; try restarting transaction

Таблица:

CREATE TABLE `counter_countries_rotates` (
  `country_id` int(11) unsigned NOT NULL,
  `date` date NOT NULL,
  `count` int(11) unsigned NOT NULL DEFAULT '0',
  UNIQUE KEY `UK_country_date` (`country_id`,`date`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8

В таблице лежат счётчики «сколько было показов в сутки по странам». Счётчики постоянно обновляются запросом вида:

INSERT INTO
`counter_countries_rotates`
SET
`country_id` = '20',
`count` = 1,
`date` = '2012-09-06'
ON DUPLICATE KEY UPDATE `count` = `count` + 1

Удалений из этой таблицы не бывает.

До поры до времени всё работает хорошо, но когда количество апдейтов одной и той же строчки в секунду превышает некое пороговое значение, запросы отваливаются с ошибкой:

Deadlock found when trying to get lock; try restarting transaction

ЧЯДНТ? Может быть стоит как-то задействовать PRIMARY индекс?

Server version: 5.1.65-log FreeBSD port: mysql-server-5.1.65