Thanks for providing us with this additional info. On my end, I was able to replicate the interaction in both Firefox and Safari. Oddly enough, it was working for me just fine in Chrome, but I'll continue to test to see if I can replicate it there as well.
Ultimately the issue being seen is related to how the 'update profile' link is populated currently by the plugin code, which uses the MailChimp account name to generate that beginning portion of the URL/link in question. In doing so, it seems like the scenario in which a MailChimp account name uses spaces, that there are some issues that occur with opening that link in certain browsers and environments. For the time being, the best bet is to use one of two options:
1) Edit the MailChimp account's name in the Account Settings area of your MailChimp account and ensure that it does not include spaces. To do this, log in to your MailChimp account, click on your name on the left-hand side in the sidebar, and click Account Settings. Then, go to Account Settings > Users & account details. On that page, scroll down to change your 'Company/organization name'. Removing any spaces from that name will ensure that the link will work as expected in all browsers.
2) Edit the plugin code and manually change the problematic portion of the URL. To do this, log in to your WP-admin area, then go to Plugins > Editor and select the MailChimp plugin. Edit the mailchimp.php file and locate the portion in the code that uses "http://$username". Replace $username with text of your choosing. Keep in mind that this will be visible in the URL that your subscribers click, so you may consider something like your company name (without spaces!).
As I'm seeing a few reports of this come into the forum, I'll be sure to escalate this to our developers to take a closer look to see if this can be handled any differently. Thanks to all that have taken the time to provide us with the info that you have. If you run into any issues in utilizing the workarounds I mentioned above, or are seeing any other symptoms/effects as a result of this issue, please feel free to post back here and I'd be happy to take a look.