apt-get autocomplete package name is broken

As stated in the comments to the other answer, first make sure that bash-completion is installed:

sudo apt-get install bash-completion

and apparently for @diapir, it helped to reinstall it:

sudo apt-get install --reinstall bash-completion

However, for me, the problem was not that bash-completion was not installed or broken, the problem was that I had accidently deleted my .bashrc file. You can get a new one by copying it from /etc/skel:

cp /etc/skel/.bashrc ~/

Type the following command:

sudo -H gedit /etc/bash.bashrc

Look for these lines:

# enable bash completion in interactive shells
# if ! shopt -oq posix; then
#  if [ -f /usr/share/bash-completion/bash_completion ]; then
#    . /usr/share/bash-completion/bash_completion
#  elif [ -f /etc/bash_completion ]; then
#    . /etc/bash_completion
#  fi
# fi

Uncomment some lines, to make it look like this:

# enable bash completion in interactive shells
if ! shopt -oq posix; then
  if [ -f /usr/share/bash-completion/bash_completion ]; then
    . /usr/share/bash-completion/bash_completion
  elif [ -f /etc/bash_completion ]; then
    . /etc/bash_completion
  fi
fi

Save, close terminal, then reopen it.

I have this issue after installing 13.04, and that's how I resolve it.

Note that output of this command:

apt-config dump | grep "Dir::Cache"

Should be something like this:

Dir::Cache "var/cache/apt";
Dir::Cache::archives "archives/";
Dir::Cache::srcpkgcache "srcpkgcache.bin";
Dir::Cache::pkgcache "pkgcache.bin";

If value of Dir::Cache::pkgcache is empty, apt will not be able to auto complete package names. Take a look at your /etc/apt/apt.conf.d/ files and search for this key to be sure that it's not set to empty string.

grep -r pkgcache /etc/apt/apt.conf.d/

Also take a look at this answer.