In my experience, they just need to cover their asses. If you tell them you have the right to print it, they’ll just make you fill out some paperwork and sign something saying as such, then they’ll do the print for you. The interaction should go something like this:
“I’d like to print this.” “I can’t do that for you, this is a copyrighted work/features copyrighted characters.” “That’s okay, I have permission from the artist and/or copyright holder to print it for personal, non-commercial use.”
If they’re still hesitant, go into more detail to put them at ease – it’s especially good if you can cite exactly which license the picture falls under. “The characters featured are all owned by Capcom, who welcome parody/fan-based derivative works, and the artist <name> licensed the work as Creative Commons Non-Commercial Share-Alike. I can sign paperwork for you stating as such.”
It’s about being firm on your position, and understanding that they’re just protecting their own asses. Kinko’s is a bit aggressive in not wanting to print potentially copyrighted works, because it’s a huge liability; don’t get frustrated with the employees about it. And if they deny you after all that, just move on – it’s their right as a business to protect their interests.
Most of my art is original pieces done by some of my friends, but I’ve run into this issue six or seven times because they’ll contain recognizable characters, but they’ve always been okay after having me sign stuff. Just go in expecting you’re going to have to.
I should note that, if you look under 18, they might deny you outright – under-age people signing forms like that is really hard to make legally binding, so it’s again their right to protect themselves.