Could not initialize class com.ibm.icu.impl.NormalizerImpl error after upgrading to app with icu4j.jar to Java 1.7.0u261+

Issue

• Our java application uses the icu4j.jar library. After updating java to 1.7.0u261 or later, we see the following error:

java.lang.NoClassDefFoundError: Could not initialize class com.ibm.icu.impl.NormalizerImpl
        at com.ibm.icu.text.Normalizer.compose(Normalizer.java:873)
        at com.ibm.icu.text.Normalizer$NFCMode.normalize(Normalizer.java:404)
        at com.ibm.icu.text.Normalizer.normalize(Normalizer.java:1111)
        at com.ibm.icu.text.Normalizer.normalize(Normalizer.java:1127)

• And before that we see:

java.lang.ExceptionInInitializerError
    at com.ibm.icu.impl.NormalizerDataReader.<clinit>(NormalizerDataReader.java:300)
    at com.ibm.icu.impl.NormalizerImpl.<init>(NormalizerImpl.java:288)
    at com.ibm.icu.impl.NormalizerImpl.<clinit>(NormalizerImpl.java:35)
    at Test.main(Test.java:8)
Caused by: java.lang.IllegalArgumentException: Invalid version number: Version number may be negative or greater than 255
    at com.ibm.icu.util.VersionInfo.getInstance(VersionInfo.java:197)
    at com.ibm.icu.impl.ICUDebug.getInstanceLenient(ICUDebug.java:65)
    at com.ibm.icu.impl.ICUDebug.<clinit>(ICUDebug.java:69)
    ... 4 more