Why does the app crash after minSdkVersion is increased on update?

Question

Android

Users massively complain that after updating from Play Market, the application stopped starting (starts and immediately crashes). However, if the application is completely uninstalled and reinstalled from the Play Store, it works fine.

In the latest update, it was necessary to raise minSdkVersion from 16 to 21.

The following is in build.gradle:

buildToolsVersion = "29.0.2"
minSdkVersion = 21 /*было 16*/
compileSdkVersion = 29
targetSdkVersion = 29

We see a bunch of such failures:

java.lang.NoSuchMethodError: 
  at okhttp3.JavaNetCookieJar.decodeHeaderAsJavaNetCookies (JavaNetCookieJar.java:91)
  at okhttp3.JavaNetCookieJar.loadForRequest (JavaNetCookieJar.java:74)
  at com.facebook.react.modules.network.ReactCookieJarContainer.loadForRequest (ReactCookieJarContainer.java:44)
  at okhttp3.internal.http.BridgeInterceptor.intercept (BridgeInterceptor.kt:75)
  at okhttp3.internal.http.RealInterceptorChain.proceed (RealInterceptorChain.kt:112)
  at okhttp3.internal.http.RetryAndFollowUpInterceptor.intercept (RetryAndFollowUpInterceptor.kt:71)
  at okhttp3.internal.http.RealInterceptorChain.proceed (RealInterceptorChain.kt:112)
  at okhttp3.internal.http.RealInterceptorChain.proceed (RealInterceptorChain.kt:87)
  at okhttp3.RealCall.getResponseWithInterceptorChain (RealCall.kt:194)
  at okhttp3.RealCall$AsyncCall.run (RealCall.kt:138)
  at java.util.concurrent.ThreadPoolExecutor.runWorker (ThreadPoolExecutor.java:1113)
  at java.util.concurrent.ThreadPoolExecutor$Worker.run (ThreadPoolExecutor.java:588)
  at java.lang.Thread.run (Thread.java:818)

What did we do wrong? And why does the application start working after a complete removal and clean installation?