I asked that he show me the iPod warranty and the language in it that supports his determination. He showed me a copy of the iPod AppleCare plan with sections 2.e.(iii) and 2.e.(v) highlighted. After reading it, I came to the conclusion that having non-Apple engraving does not necessarily void the warranty. I explained my reasoning, but couldn't convince him that his claims weren't supported by the warranty. (Before leaving the store, I probably let my frustration show a bit too much, and for that I apologize to both sales people.)Link
I have since spoken to Apple Customer Service on the phone, and though they can't of course comment on my issue without seeing the Shuffle first, they were able to tell me that there is no blanket policy stating that non-Apple laser engraving voids the warranty, and that any such determination is up to the technician examining the unit, guided by the terms and conditions of the warranty. They recommended I take this issue up with the store manager.