Are rules limited by user roles?
I've definitely run into problems with this before and it's pretty annoying.. 

One possible way out of it is to create an extra role with the required permission and in rules, add it, force save user, do stuff, remove role.