Did you have the pressurization controller set to 500 feet above your cruise altitude as is recommended?
You say the cabin was at max differential. At cruise, setting the controller to +500 feet means that the cabin will be a couple of tenths less than maximum. If the cabin is at maximum differential, and the outflow and safety vales are not set to the same maximum differential setting (highly unlikley) then they will be fighting each other for control of the maximum differential in the cabin.
Try setting the controller a little higher and getting a slightly lower differential.
If that does not fix it, look for a sticky valve or something blocking the airflow to them.
Bill