SSL Verification Fails After Upgrade

I got Google TTS working a couple of days ago. Now I’ve upgraded to Home Assistant 0.68 and updated Ubuntu to 18.04. I don’t know which of the two is causing this but I’m getting errors like the ones below in my logs and the service isn’t working. It seems to be a more general problem since the Spotify integration also is failing because of SSL issues.
Does anyone have a pointer how I can debug and fix this issue? It seems that on a system level at least SSL is working okay.

2018-04-29 09:58:10 ERROR (MainThread) [homeassistant.core] Error executing service <ServiceCall tts.google_say: entity_id=['media_player.vlc'], message=This is a test>
Traceback (most recent call last):
  File "/usr/local/lib/python3.6/dist-packages/urllib3/contrib/pyopenssl.py", line 441, in wrap_socket
    cnx.do_handshake()
  File "/usr/lib/python3/dist-packages/OpenSSL/SSL.py", line 1808, in do_handshake
    self._raise_ssl_error(self._ssl, result)
  File "/usr/lib/python3/dist-packages/OpenSSL/SSL.py", line 1548, in _raise_ssl_error
    _raise_current_error()
  File "/usr/lib/python3/dist-packages/OpenSSL/_util.py", line 54, in exception_from_error_queue
    raise exception_type(errors)
OpenSSL.SSL.Error: [('SSL routines', 'tls_process_server_certificate', 'certificate verify failed')]

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/usr/local/lib/python3.6/dist-packages/urllib3/connectionpool.py", line 601, in urlopen
    chunked=chunked)
  File "/usr/local/lib/python3.6/dist-packages/urllib3/connectionpool.py", line 346, in _make_request
    self._validate_conn(conn)
  File "/usr/local/lib/python3.6/dist-packages/urllib3/connectionpool.py", line 850, in _validate_conn
    conn.connect()
  File "/usr/local/lib/python3.6/dist-packages/urllib3/connection.py", line 326, in connect
    ssl_context=context)
  File "/usr/local/lib/python3.6/dist-packages/urllib3/util/ssl_.py", line 329, in ssl_wrap_socket
    return context.wrap_socket(sock, server_hostname=server_hostname)
  File "/usr/local/lib/python3.6/dist-packages/urllib3/contrib/pyopenssl.py", line 448, in wrap_socket
    raise ssl.SSLError('bad handshake: %r' % e)
ssl.SSLError: ("bad handshake: Error([('SSL routines', 'tls_process_server_certificate', 'certificate verify failed')],)",)

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/usr/local/lib/python3.6/dist-packages/requests/adapters.py", line 440, in send
    timeout=timeout
  File "/usr/local/lib/python3.6/dist-packages/urllib3/connectionpool.py", line 639, in urlopen
    _stacktrace=sys.exc_info()[2])
  File "/usr/local/lib/python3.6/dist-packages/urllib3/util/retry.py", line 388, in increment
    raise MaxRetryError(_pool, url, error or ResponseError(cause))
urllib3.exceptions.MaxRetryError: HTTPSConnectionPool(host='translate.google.com', port=443): Max retries exceeded with url: / (Caused by SSLError(SSLError("bad handshake: Error([('SSL routines', 'tls_process_server_certificate', 'certificate verify failed')],)",),))

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "/usr/local/lib/python3.6/dist-packages/homeassistant/core.py", line 1002, in _event_to_service_call
    await service_handler.func(service_call)
  File "/usr/local/lib/python3.6/dist-packages/homeassistant/components/tts/__init__.py", line 134, in async_say_handle
    options=options
  File "/usr/local/lib/python3.6/dist-packages/homeassistant/components/tts/__init__.py", line 300, in async_get_url
    engine, key, message, use_cache, language, options)
  File "/usr/local/lib/python3.6/dist-packages/homeassistant/components/tts/__init__.py", line 313, in async_get_tts_audio
    message, language, options)
  File "/usr/local/lib/python3.6/dist-packages/homeassistant/components/tts/google.py", line 85, in async_get_tts_audio
    token.calculate_token, part)
  File "/usr/lib/python3.6/concurrent/futures/thread.py", line 56, in run
    result = self.fn(*self.args, **self.kwargs)
  File "/home/homeassistant/.homeassistant/deps/lib/python3.6/site-packages/gtts_token/gtts_token.py", line 28, in calculate_token
    seed = self._get_token_key()
  File "/home/homeassistant/.homeassistant/deps/lib/python3.6/site-packages/gtts_token/gtts_token.py", line 58, in _get_token_key
    response = requests.get("https://translate.google.com/")
  File "/usr/local/lib/python3.6/dist-packages/requests/api.py", line 72, in get
    return request('get', url, params=params, **kwargs)
  File "/usr/local/lib/python3.6/dist-packages/requests/api.py", line 58, in request
    return session.request(method=method, url=url, **kwargs)
  File "/usr/local/lib/python3.6/dist-packages/requests/sessions.py", line 508, in request
    resp = self.send(prep, **send_kwargs)
  File "/usr/local/lib/python3.6/dist-packages/requests/sessions.py", line 618, in send
    r = adapter.send(request, **kwargs)
  File "/usr/local/lib/python3.6/dist-packages/requests/adapters.py", line 506, in send
    raise SSLError(e, request=request)
requests.exceptions.SSLError: HTTPSConnectionPool(host='translate.google.com', port=443): Max retries exceeded with url: / (Caused by SSLError(SSLError("bad handshake: Error([('SSL routines', 'tls_process_server_certificate', 'certificate verify failed')],)",),))

Just in case anybody else runs into this:
The cause was that I was running HomeAssistant outside of a python virtual environment before and now moved it into one. The leftover dependencies under deps/ were causing this problem. After deleting everything in that directory, everything is working fine now.