Failure while running SQLCMD with -E option for a AD user

I am trying to run SQLCMD with E option as shown below,

sqlcmd -E -S <MY_SQL_SERVER> -Q "<some script>". 

However, it fails with an below error,

"Login failed for user ‘<Domain_name><user_name>’. Reason: Could not find a login matching the name provided."

The SQL server uses windows authentication and has a login setup. This login is then mapped with a windows user group. This AD user is a part of the windows user group.

Any idea why such problem can come? and how to resolve this?