Which user does the Rules module execute as?
And here is a module that could assist:

Rules switch user


  This module adds two new Rules actions:
  
  
  Switch to another user
  Switch back from another user
  
  
  These actions could be useful when you have an operation that you want
  an unprivileged user to use but it fails because the user doesn't have
  sufficient permissions.


Create a fictitious user with sufficient permissions and switch to this user when performing the Rules action and switch back again when done.

EDIT This answer is just a workaround and does not speak to the question directly, namely why the current permissions doled out are not allowing the Rule to execute successfully.