This isn't a Wordpress Magic error but may occur while using it.
Certain hosting providers use a default collation (such as latin1_swedish_ci) that is different from the standard one (utf8_general_ci). In particular, we know that JustHost uses the latin1 collation as opposed to utf8.
Unfortunately, trying to change the collation of your Wordpress database after it is already installed may prove difficult. The best way is to ensure that you install Wordpress with a database that is using the correct collation from the get-go. In order to do this, do the following:
Create a new database in your hosting cPanel and set the collation to utf8_general_ci. Also obviously create and link a database user with full privileges to the database. How to do this is beyond the scope of this guide - please contact your hosting provider for assistance if need be.
Download the latest version of Wordpress and unzip the files
Edit wp-config.php (if it doesn't exist, rename wp-config-sample.php to wp-config.php) with notepad or similar
Change the line define('DB_COLLATE', ''); to define('DB_COLLATE', 'utf8_general_ci');
Upload the entire Wordpress install package to your server and run the setup as you normally would.
You're done! You shouldn't have any further problems with collation. Special thanks to Forey (aka bamtel) at the My Affiliate Apprentice for working this one out.