That's just paranoia, thanks to the RIAA, MPAA and other whiners that have been loudly complaining about copyrights.
There's something called "fair use". If you're a graphic designer, it's very common to use "comp" images. You sure as hell don't pay for those image rights until your client gives final approval and says "yes, we'll go with that design". Then you go ahead and pay for the images you use in the final product.
Kinko's and other print shops doing "one-offs" shouldn't be saying anything. But they are so scared now they are taking the "better safe than sorry" side. Unless a customer is asking for multiple copies of an item, Kinko's is being ridiculous.
I work on many projects that use high-profile brand names and characters. I CANNOT imagine the trouble I'd have to go through if I required a "release form" for each and every time I use a copyrighted or trademarked image. My projects which are "due tomorrow" would likely get delayed by weeks, since that's how long it usually takes to get "upper management" types at the big brand companies to do something as simple as sign and fax through a form.
MAMEIAC: Call Kinko's and tell them your marquee is a "proof of concept" for a client, and that they are holding up your schedule and your client is getting angry with you. Tell them if it was for commercial use, you'd be ordering hundreds, not just one.