I finally figured out the issue with this one and it was related to the domain name..
Our domain name is something like the following: EXAMPLE.LOCAL
And every time we login to a remote session or even when we are logging in through /RDWeb/Pages/en-US/login.aspx
we can not login with the first half of the domain name (in this case EXAMPLE).
However, for some weird reason, we could not update the password using the full name of the domain, we could only change the password by using the first half of the name.
To make it even more clear here is an example below:
Username: USER1
Domain Name: EXAMPLE.LOCAL
to login with RDP or even on RDWA, this is the case:
EXAMPLE\USER1
Does Not Work!
EXAMPLE.LOCAL\USER1
Works!
However, to change the password on RDWA, this is the case:
EXAMPLE\USER1
Works!
EXAMPLE.LOCAL\USER1
Does Not Work!
I am putting this out here just in case somebody else faces this issue, because this has baffled me for at least 2 weeks until I figured it out (embarrassingly enough, through a typo).