I also confirmed the API Key is valid using the mailchimp API PHP class as defined here: https://www.inkthemes.com/learn-how-to-use-mailchimp-api-in-wordpress-plugin/
<?php
require_once 'MCAPI.class.php';
$apikey='xxxxxxxxxxxxxxxxxxxxxxx'; // Enter your MailChimp API key here
$api = new MCAPI($apikey);
$retval = $api->lists();
foreach ($retval['data'] as $list){
echo $list['name']; echo " "; echo " "; echo " "; echo "&nbasp"; echo " ";
echo $list['id'];
echo "<br />";
}
?>
I am having the same issue. I am running Version 1.5.3 of the MailChimp plugin. I am on WordPress v3.6.1 on PHP 5.4. I have tried with multiple API keys now and I am the MailChimp account owner.