I have the same problem of the original poster (no autocompletion with sudo apt-get install), but I do not have the /etc/apt/apt.conf file. This is a standard install of Ubuntu Jaunty from the regular desktop CD.
I tried the command "apt-cache pkgname gnome-" without the sudo, as suggested above, but I get a "E: Invalid operation pkgname" error. I have to use "pkgnames" with the "s" to make it work, and then it gives me the list of packages even without the sudo. Could this be the problem? Is there any way to fix it?