I would recommend installing the current version of approx if that's not too disruptive. The approx-gc program has been replaced with a simple find script that just removes old files, rather than trying to determine whether they're still referenced from Packages files (that was the source of several bugs).
If you can locate a package you know is in your approx cache, and can reproduce the problem (missing the cache) by doing an "apt-get install --reinstall ...", please send the log corresponding to that. I can't see where the problem is from the portion you posted.
