Just had this error, solved by downloading the Android SDK Command-line Tools (latest) on Android Studio, under Preferences > Appearance & Behavior > System Settings > Android SDK > SDK Tools and re-running flutter doctor --android-licenses
Finally, add the new tools to your PATH, in your .bashrc, .zshrc or similar, before the obsolete tools:
export PATH=$PATH:$ANDROID_HOME/cmdline-tools/latest/bin