Error returned on newsletter sign-up via profiles in Wordpress
Since this works when you are logged into WordPress it looks like it might be a permissions issue. Is the redirect after submission set in the profile advanced settings? You may want to check the page being redirected to to make sure anonymous users have access to it. Also check the permissions for anonymous users under 'Administer>Users and Permissions>Permissions (access control)' click on WordPress Access Control. Particularly the permissions around profiles.

What version of  WordPress &amp; CiviCRM are you running? Since it was working OK prior to recent updates when was your last CiviCRM update?

Hope this helps.