MySQL has a bug in which it counts bytes, not characters, when calculating the key length.
Computers have a _bug_ too, where they count bytes, not characters, well... everywhere.
Thus, something that works fine in a single-byte-per-character character set suddenly fails when you switch to a multi-byte character set such as utf-8.
The limit doesn't exist with new MySQL versions in MyISAM and old versions in InnoDB. If you're getting that error, there's huge chance you have InnoDB disabled.
One solution (besides abandoning utf-8 or MySQL) is to redefine the index in question to use smaller values. A quick google search found this example:
Or use InnoDB. Or use fresh MySQL version.