AADSTS65001: The user or administrator has not consented to use the application

Using a native client app , we are calling a middler tier service which is also registered in AAD. This middle tier service internally takes dependencies on other apps. Recently added a new web resource to be accessed by the middle tier service in API permissions. Admin consent not required and user can consent all apps in User consent settings.

Consistently getting the following error -
Send an interactive authorization request for this user and resource.\r\nTrace ID: f206e1a8-7a3c-4b9d-8918-3f23e7611100\r\nCorrelation ID: 3012cab0-8e6e-452d-9a9b-ce297a5d084b\r\nTimestamp: 2021-09-09 07:28:21Z"

Also tried to consent through following code but not seeing the newly added permissions to the Middle Tier service.

AuthenticationResult authResult = authenticationContext.AcquireTokenAsync(
Audience,
NativeAppClientId,
new Uri(NativeAppRedirectUrl),
new PlatformParameters(PromptBehavior.Auto),
UserIdentifier.AnyUser,
"prompt=consent").GetAwaiter().GetResult();