Android 14 ForegroundServiceStartNotAllowedException: Service.startForeground() not allowed

Question

Just updated one of my Android apps to work with Target sdk of 34. My app requires the use of a foreground Service, that is the SPECIAL_USE type since none of the other foreground types work. The App Store did approve of it which is nice.

But since then I've been seeing an influx of crashes from Android 14 users at this block in onStartCommand

        if (Build.VERSION.SDK_INT < 34) {
            startForeground(NOTIFICATION_NUMBER++, getNotification(!enable_trace_mode, app_bundle));
        } else {
            startForeground(NOTIFICATION_NUMBER++, getNotification(!enable_trace_mode, app_bundle), ServiceInfo.FOREGROUND_SERVICE_TYPE_SPECIAL_USE);
        }


        return START_STICKY;

with the following stack trace

Caused by android.app.ForegroundServiceStartNotAllowedException: Service.startForeground() not allowed due to mAllowStartForeground false: service com.my.app/.NiceOverlayService
       at android.app.ForegroundServiceStartNotAllowedException$1.createFromParcel(ForegroundServiceStartNotAllowedException.java:54)
       at android.app.ForegroundServiceStartNotAllowedException$1.createFromParcel(ForegroundServiceStartNotAllowedException.java:50)
       at android.os.Parcel.readParcelableInternal(Parcel.java:4882)
       at android.os.Parcel.readParcelable(Parcel.java:4864)
       at android.os.Parcel.createExceptionOrNull(Parcel.java:3064)
       at android.os.Parcel.createException(Parcel.java:3053)
       at android.os.Parcel.readException(Parcel.java:3036)
       at android.os.Parcel.readException(Parcel.java:2978)
       at android.app.IActivityManager$Stub$Proxy.setServiceForeground(IActivityManager.java:7214)
       at android.app.Service.startForeground(Service.java:862)
       at com.my.app.NiceOverlayService.onStartCommand(NiceOverlayService.java:76)
       at android.app.ActivityThread.handleServiceArgs(ActivityThread.java:5268)
       at android.app.ActivityThread.-$$Nest$mhandleServiceArgs()
       at android.app.ActivityThread$H.handleMessage(ActivityThread.java:2531)
       at android.os.Handler.dispatchMessage(Handler.java:106)
       at android.os.Looper.loopOnce(Looper.java:230)
       at android.os.Looper.loop(Looper.java:319)
       at android.app.ActivityThread.main(ActivityThread.java:8893)
       at java.lang.reflect.Method.invoke(Method.java)
       at com.android.internal.os.RuntimeInit$MethodAndArgsCaller.run(RuntimeInit.java:608)
       at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:1103)

I've been banging my head trying to reproduce this crash but to no avail. According to log reports it's occurring within the first second the app starts up, which is strange because my Service doesn't start until much later when the user permits it. I'm thinking it could be a memory issue but I'm not 100% sure on that. I have seen other people here mention a similar problem but no surefire fix for it. Does anyone know a solution to this?