I also had same problem with different environments, but they are all now working.
My environments that I tested are:
WP 3.0.5 + mysql 5.0.91-community-log + NextGen 1.7.4
WP 3.1 + mysql 5.0.91-community-log + NextGen 1.7.4
WP 3.1 + mysql 5.5.8-log + NextGen 1.7.4
My solution is to change both DB_CHARSET and DB_COLLATE in wp-config.php:
/** Database Charset to use in creating database tables. */
define('DB_CHARSET', 'utf8');
/** The Database Collate type. Don't change this if in doubt. */
define('DB_COLLATE', '');
Previously it was:
/** Database Charset to use in creating database tables. */
define('DB_CHARSET', 'utf8_unicode_ci');
/** The Database Collate type. Don't change this if in doubt. */
define('DB_COLLATE', 'utf8_unicode_ci');
Hope this works for you…