I believe that I have found a conflict between your MailChimp Newsletter Integration plugin and the official MailChimp List Subscribe Form plugin.
I am using the latest versions of each:
MailChimp Newsletter Integration version 1.1.1 (shows up as MailChimp Sync in plugin list on WP)
MailChimp List Subscribe Form version 1.2.1 available here - http://wordpress.org/extend/plugins/mailchimp/
I am using a WPMU setup, activating MailChimp List Subscribe Form on the main blog only and a network activate for MailChimp Newsletter Integration.
When both are active, the drop down box for MailChimp List Subscribe Form is empty - showing no lists - after the API key is entered and verified. Deactivating MailChimp Newsletter Integration causes MailChimp List Subscribe Form to work again (showing my mailing lists in dropdown box). I've tried this several times, deactivating/activating MailChimp Newsletter Integration.
This following thread may be relevant: