I think I'm still hitting this issue 10 years later. On Ubuntu 18.04.1 I was trying to add the 18.04.2 CD as a source to upgrade from. It would seem to work and I could upgrade single packages, but if I would do an upgrade I would get "File not found" for every package even though the paths being referenced were correct. The "cdrom://" protocol being sort of obtuse really made debugging it difficult. I randomly noticed in my output from "apt-config dump": Acquire::cdrom::mount "/media/cdrom/"; even though apt-cdrom automatically mounted the disk to "/media/apt". I decided to try symlinking "/media/cdrom" to "/media/apt" and it started working properly!
Hope this helps.
-Jesse