After installing and activating the Mailchimp plugin v1.2.4 I could not see the 'Mailchimp Setup' menu item. I've used the plugin on other installs and never had this problem. I eventually solved the problem by changing the following in mailchimp.php :
define('MCSF_CAP_THRESHOLD', 'edit_plugins');
to
define('MCSF_CAP_THRESHOLD', 'install_plugins');
I'm not really sure why I had to do this, since my user account is an Administrator (WP 3.1.2 single-site mode) and 'edit_plugins' should definitely work.