On servers with default isolation level set to READ COMMITTED or READ UNCOMMITTED and log-bin enabled the permission check in pt-table-sync will fail as it sets replication mode to statement based replication and then checks whether the user has sufficient permissions to execute a "DELETE FROM table LIMIT 0".
This fails on InnoDB tables as DELETE in READ [UN]COMMITTED is not safe for statement based replication.
Current workaround would be to call pt-table-sync with --transaction which will explicitly set isolation level REPEATABLE READ,
IMHO this should always be set though as it also has an effect in auto commit mode outside of transactions as single statements by themselves will still be transactions of their own, and so be affected by the "DELETE in READ [UN]COMMITTED is not safe for statement based replication" limitation.
The error message raised by pt-table-sync is also very confusing in this context as it only reports that the users permissions are insufficient (even for users with ALL PRIVILEGES WITH GRANT OPTION) and does not reveal the actual error message and so giving no hints towards the actual problem.
See also last two entries (comment #8 and #9) on http:// code.google. com/p/maatkit/ issues/ detail? id=1029