I saw this on /. a while back and this thread reminded me of it.  Apparently this guy has done some 
testing on old CD-Rs that he had
burned, and most of them read just fine, with the exception of some of the ones that he had put 
adhesive labels on.

http://www.informationweek.com/story/showArticle.jhtml?articleID=15800263&pgno=1

Here is part another white paper on the subject that refers to the same problem of adhesive labels.

http://www.osta.org/technology/cdqa11.htm

Has anyone here experienced this problem with using adhesive labels on their CDs?

Gene