diff --git a/Lib/_strptime.py b/Lib/_strptime.py
index 5ea59ed..9e7823a 100644
--- a/Lib/_strptime.py
+++ b/Lib/_strptime.py
@@ -295,17 +295,16 @@
     """Return a time struct based on the input string and the format string."""
     global _TimeRE_cache, _regex_cache
     with _cache_lock:
-        time_re = _TimeRE_cache
-        locale_time = time_re.locale_time
-        if _getlang() != locale_time.lang:
+        if _getlang() != _TimeRE_cache.locale_time.lang:
             _TimeRE_cache = TimeRE()
-            _regex_cache = {}
+            _regex_cache.clear()
         if len(_regex_cache) > _CACHE_MAX_SIZE:
             _regex_cache.clear()
+        locale_time = _TimeRE_cache.locale_time
         format_regex = _regex_cache.get(format)
         if not format_regex:
             try:
-                format_regex = time_re.compile(format)
+                format_regex = _TimeRE_cache.compile(format)
             # KeyError raised when a bad format is found; can be specified as
             # \\, in which case it was a stray % but with a space after it
             except KeyError, err:
diff --git a/Lib/test/test_strptime.py b/Lib/test/test_strptime.py
index 56e1ab8..48e6b31 100644
--- a/Lib/test/test_strptime.py
+++ b/Lib/test/test_strptime.py
@@ -505,6 +505,23 @@
         self.failIfEqual(locale_time_id,
                          id(_strptime._TimeRE_cache.locale_time))
 
+    def test_TimeRE_recreation(self):
+        # The TimeRE instance should be recreated upon changing the locale.
+        locale_info = locale.getlocale(locale.LC_TIME)
+        try:
+            locale.setlocale(locale.LC_TIME, ('en_US', 'UTF8'))
+        except locale.Error:
+            return
+        try:
+            _strptime.strptime('10', '%d')
+            first_time_re_id = id(_strptime._TimeRE_cache)
+            locale.setlocale(locale.LC_TIME, ('de_DE', 'UTF8'))
+            _strptime.strptime('10', '%d')
+            second_time_re_id = id(_strptime._TimeRE_cache)
+            self.failIfEqual(first_time_re_id, second_time_re_id)
+        finally:
+            locale.setlocale(locale.LC_TIME, locale_info)
+
 
 def test_main():
     test_support.run_unittest(