update error on alter table date_format add unique key (format, type)

When trying to update, I got the following error:
user warning: Specified key was too long; max key length is 1000 bytes query: ALTER TABLE date_formats ADD UNIQUE KEY formats (format, type) in /home/cd6/htdocs/includes/database.mysql-common.inc on line 403.

The following queries were executed
date_api module
Update #6004
ALTER TABLE {date_format} RENAME TO {date_formats}
ALTER TABLE {date_formats} DROP KEY format
Failed: ALTER TABLE {date_formats} ADD UNIQUE KEY formats (format, type)
Update #6005
ALTER TABLE {date_formats} CHANGE format format VARCHAR( 100 ) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL
ALTER TABLE {date_format_locale} CHANGE format format VARCHAR( 100 ) CHARACTER SET utf8 COLLATE utf8_bin NOT NULL

I must admit we've been having a fair bit of trouble with this module due to issues with view sorts, and so I'm not sure of the history of installs, uninstalls, dev installs, etc. I will note that when I check the info schema for the table, I see that the two relevant columns are defined:
format varchar 100
type varchar 255
which means it's hard to understand where 1000 bytes comes from. Notable is that the collations are a bit weird: utf8_bin for format, and utf_general_ci for type. The character octet length is thus 300 and 765. You should probably set the collations to latin, reduce the length of the type field, or perhaps change so that you index only part of it??