Wow, that's a really strange and unhelpful error message. Yuck.
It looks like you might be able to fix this by running the following query on the database (e.g, through PHPMyAdmin):
ALTER DATABASE COLLATE = utf8_unicode_ci;
It's not clear whether the installer will be satisfied with this, though, or whether it actually requires the collation to be set on the server level, which is more difficult to change.