Certbot fails with AttributeError: 'module' object has no attribute 'Locale'

I setup a new server a couple of months ago, running Ubuntu 18.04 LTS. I successfully installed certbot and created my certificates using the cloudflare DNS plugin.

It's now getting to be time for renewal, but when I run certbot renew (or various other certbot commands) I get the following error

# certbot renew
/usr/local/lib/python2.7/dist-packages/cryptography/__init__.py:39: CryptographyDeprecationWarning: Python 2 is no longer supported by the Python core team. Support for it is now deprecated in cryptography, and will be removed in a future release.
  CryptographyDeprecationWarning,
Traceback (most recent call last):
  File "/usr/local/bin/certbot", line 7, in <module>
    from certbot.main import main
  File "/usr/local/lib/python2.7/dist-packages/certbot/main.py", line 2, in <module>
    from certbot._internal import main as internal_main
  File "/usr/local/lib/python2.7/dist-packages/certbot/_internal/main.py", line 21, in <module>
    from certbot._internal import cert_manager
  File "/usr/local/lib/python2.7/dist-packages/certbot/_internal/cert_manager.py", line 16, in <module>
    from certbot._internal import storage
  File "/usr/local/lib/python2.7/dist-packages/certbot/_internal/storage.py", line 79, in <module>
    def add_time_interval(base_time, interval, textparser=parsedatetime.Calendar()):
  File "/usr/local/lib/python2.7/dist-packages/parsedatetime/__init__.py", line 270, in __init__
    self.ptc = Constants()
  File "/usr/local/lib/python2.7/dist-packages/parsedatetime/__init__.py", line 2381, in __init__
    self.locale = get_icu(self.localeID)
  File "/usr/local/lib/python2.7/dist-packages/parsedatetime/pdt_locales/icu.py", line 56, in get_icu
    result['icu'] = icu = pyicu.Locale(locale)
AttributeError: 'module' object has no attribute 'Locale'

The output of locale -a is

# locale -a
C
C.UTF-8
en_US.utf8
POSIX

I have also run pip install cryptography --upgrade but that didn't change anything.

I am not sure what changed that broke it, and I can't figure out how to get it working!

Check to make sure you don't have a /usr/local/bin/certbot script

I had one, I think I cloned the certbot auto package on this system once. And after removing it and getting back to running /usr/bin/certbot I no longer get this error.

Also seems certbot is python 3 app, the correct certbot script starts out:

#!/usr/bin/python3
# EASY-INSTALL-ENTRY-SCRIPT: 'certbot==0.31.0','console_scripts','certbot'
__requires__ = 'certbot==0.31.0'
import re
import sys
from pkg_resources import load_entry_point

if __name__ == '__main__':
    sys.argv[0] = re.sub(r'(-script\.pyw?|\.exe)?$', '', sys.argv[0])
    sys.exit(
        load_entry_point('certbot==0.31.0', 'console_scripts', 'certbot')()
    )