Users on windows 2008 R2 server cannot change own password
Solution 1:
I assume the GPO you were changing was the Default Domain GPO; that is the only one that affects domain userid's. GPO's on OU's only affects local accounts on domain-member computers that are in that OU.
Although domains in Win2008 mode can do OU-based policy however I have not researched how nor the details.