Hi Karl,
This is absolutely a vibration problem. Funny how a $400.00 cd/radio unit doesn't employ read-ahead technology found in a $50.00 portable cd player - grrr. Anyway, here's a couple of things to try...
Slide the unit out (no need to disconnect the power) and check that the mounting rails/housing in-dash are secure to the rest of the inner dash.
Also make sure the wiring harness was/is not crammed tight under the unit.
If that's not the problem, you can try as the dealer suggested to 'snug up' the unit, but I would use foam insulation tape like what you would use for windows and doors, and only a couple of strips along the bottom of the housing where the foam makes 'soft' contact with the unit. (ie: not fully compressed).
The reason that the cd goes dead for a few seconds is because the "spinner" and the lens have their own suspension within the radio unit - basically they hang independantly from springs located on each corner. When you jar the unit it takes a couple of seconds for the lens to relocate its position on the disc. If you can reduce the vibration reaching the entire unit this should allow the internal suspension to do it's job.
Good luck,
Armie

--
'94 850 154000kms '86 760GLE 272000kms 95 Silverado4x4