What does MySQL mean by "Major Version", and is MySQL replication supported between 5.1 and 5.6?
I've confirmed this is a bug with MySQL/Oracle Support. They will update the public tickets when the internal fixes are ready.

To summarize: MySQL replication is only supported between one release level (the second digit) and the next; e.g. between MySQL 5.1 and 5.5; 5.5 and 5.6 but not between MySQL 5.1 and 5.6. The documentation is mistaken when it says "MySQL supports replication from one major version to the next higher major version."* They mean release level or release series number, not major version. That is, unless they change the terminology in the future.

Replication between 5.1 and 5.6 might work, but it's not supported and not well tested. It's best to for replication servers to stay within one release level of each other, and to use the latest version of your 5.x release.

The bug reports are:


"Section should be more clear about 5.5 and 5.6 versions". Now, the documentation is more clear:



  MySQL supports replication from one release series to the next higher
  release series. For example, you can replicate from a master running
  MySQL 5.5 to a slave running MySQL 5.6, from a master running MySQL
  5.6 to a slave running MySQL 5.7, and so on.



A second private bug which I'll add once the bug is made public.