The problem with your set-up (from an SEO standpoint) is that search engines don't accept cookies, so whenever a bot follows a link to your root domain, it'll be sent to your English content. Hopefully there's an abundance of links to the other language content, too, but in my experience this situation nevertheless seems to lie at the root of a lot of geotargeting difficulties.
This might be why Google recommend that you "Avoid automatic redirection based on the user’s perceived language. These redirections could prevent users (and search engines) from viewing all the versions of your site."
I have a client whose /en/ pages (they have umpteen other languages on their domain) show up for most searches globally, despite there being good region-specific alternatives, and despite employing Google's rel="alternate" method. The only remaining cause appears to be that they default to /en/ at root in the absence of an Accept-Language HTTP header (search engines don't use send one).
In short, I'd be inclined to allow users to manually choose their language and then set a cookie, rather than redirect.