LDAPS integration fails with "Message objects do not support str() because they may contain non-ascii characters."

Issue

When configuring keystone with LDAPS, all calls to keystone fail with:

# keystone user-list
Authorization Failed: An unexpected error prevented the server from fulfilling your request. (HTTP 500)

and logs this in /var/log/keystone/keystone.log:

2014-12-04 09:31:38.332 11530 ERROR keystone.common.wsgi [-] Message objects do not support str() because they may contain non-ascii characters. Please use unicode() or translate() instead.
2014-12-04 09:31:38.332 11530 TRACE keystone.common.wsgi Traceback (most recent call last):
2014-12-04 09:31:38.332 11530 TRACE keystone.common.wsgi   File "/usr/lib/python2.7/site-packages/keystone/common/wsgi.py", line 396, in __call__
2014-12-04 09:31:38.332 11530 TRACE keystone.common.wsgi     response = request.get_response(self.application)
...
2014-12-04 09:31:38.332 11530 TRACE keystone.common.wsgi     raise UnicodeError(msg)
2014-12-04 09:31:38.332 11530 TRACE keystone.common.wsgi UnicodeError: Message objects do not support str() because they may contain non-ascii characters. Please use unicode() or translate() instead.
2014-12-04 09:31:38.332 11530 TRACE keystone.common.wsgi 
2014-12-04 09:31:38.337 11530 INFO eventlet.wsgi.server [-] 192.168.2.63 - - [04/Dec/2014 09:31:38] "POST /v2.0/tokens HTTP/1.1" 500 291 0.016902