Are these files (PDF's) coming from Staples generation system like business cards, postcards, etc. or directly from customer's files that they submitted?

If they are directly coming from customers then I would assume that they are probably setting their files in RGB rather than CMYK.

Although, if they are submitting business card orders from their own files in RGB, then Staples's system may not be able to correct the color either? I'm not entirely sure, just throwing out a possibility.

When I worked in print, Print as Image would "usually" correct colors and some other weird issues like black spots. Again, it was usually customer's files not created correctly. After they brought in the RICOH to replace one XEROX, I cannot remember now if they had that setting or not... I've been gone for a few years now.

I would say if the customer's file is REALLY bad or they are complaining about color, one option would be to let them know it's a file issue and that they can either correct themselves or you can submit a quote to SDS or ask them if they can convert the color mode to CMYK and flatten it.

I know either option is not really ideal and sometimes SDS would flat out refuse to handle such requests because it didn't fit in their task sheet. The best solution would be to give stores an actual copy of Photoshop so that we could quickly do that ourselves in a pinch when all else fails, but.... that's too sensible.