You may have an issue with your /etc/apt/sources.list file which is where the apt command looks for the installation of new packages.