Emm,
in your config.php file add this
dbcollation' => 'utf8_unicode_ci'
It wont convert your database to Barracuda but at least will let you install moodle.
So far there is only one shared host I know supporting Barracuda, that is why I switched to them leaving bluehost after 15 years with them, and specially since they moved their support to India, their support people have no clue what customer is requiring and every person has different thing to say about your queries.