User rights not being assigned: Is this an issue with Group Policy or Active Directory?

I've tried using GPUdate but it has not worked. Everything seems to be OK, but it isn't. I have only been in the job for a couple of weeks, and I'm struggling to sort this out. I need to correct this problem soon, any help on this one gratefully accepted.

This doesn't sound like a Group Policy problem to me. It sounds like a password strength problem. My suggestion: using Active Directory Users and Computers, simply right-click over the username and reset the password to something that meets the strength requirements. I would suggest contacting your domain admin to ensure you understand what the strength requirements are. It's conceivable that the "upgraded accounts" weren't subject do this requirement during the upgrade, but now that you're trying to reset the password, only now are you seeing the requirement. Hope that helps.