Odd. I wasn't aware there was a permission for that.

Only one role is having problem with Saved Search Advanced PDF printing

Maybe it's view on setup tab for the advanced PDF templates?