I found the solution based on the discussion available at https://unix.stackexchange.com/questions/377345/installing-arm-none-eabi-gcc and the documentation available on https://mynewt.apache.org/latest/get_started/native_install/cross_tools.html#installing-the-arm-cross-toolchain.

The name and structure of the software changed over time. The arm-none-eabi-gcc is gcc-arm-none-eabi now, and so on.

$ sudo apt-get remove binutils-arm-none-eabi gcc-arm-none-eabi
$ sudo add-apt-repository ppa:team-gcc-arm-embedded/ppa
$ sudo apt-get update 
$ sudo apt-get upgrade
$ sudo apt-get install gcc-arm-none-eabi
$ sudo apt-get install gdb-arm-none-eabi 

And finally, to verify the downloads, you can run the following commands:

arm-none-eabi-gcc --version
arm-none-eabi-g++ --version
arm-none-eabi-size --version 

You can download a functional toolchain from developer.arm.com and install it manually after removing your existing gcc-arm-none-eabi package.

Go to that website, click the "Download" button and get: gcc-arm-none-eabi-7-2018-q2-update-linux.tar.bz2. Save it in your home directory.

Make sure you've uninstalled the old Ubuntu packages.

sudo apt remove binutils-arm-none-eabi gcc-arm-none-eabi libnewlib-arm-none-eabi

Untar the new package in your home directory:

tar -xjvf gcc-arm-none-eabi-7-2018-q2-update-linux.tar.bz2

Add the new toolchain to your path:

export PATH=$PATH:/home/(your user)/gcc-arm-none-eabi-7-2018-q2-update/bin/

At this point you should have a working ARM compiler and toolchain. (For the Unix newbies: if you close the terminal and open a new one, you'll have to re-run the export PATH statement so the compiler will get picked up again.)

To check if the compiler is installed:

gcc --version

I assuming you are running Debian wheezy based on the error message.

I would recommend upgrading to Debian 8 jessie and follow the installation instructions at the Debian wiki. I also suggests that you remove the dead ppa url in your apt sources before upgrading.

If upgrading is not an option, you might be able to find the binaries for your architecture or install them manually.

Note: In Debian 9 stretch, which is currently in testing, this should no longer be an issue.

It turned out that ARM decided to make our life easier (sarcasm) by deprecating the use of PPA - their page at launchpad now has an anouncement: "... all new binary and source packages will not be released on Launchpad henceforth ...".

So, to make use of their latest arm-none-eabi-gdb you have to install gcc-arm-embedded manually.

Remove arm-none-eabi-gcc from your system:

sudo apt remove gcc-arm-none-eabi

Download latest version (Linux x86_64 Tarball) from their website, check its MD5. Unpack it into some directory. I used /usr/share/ :

sudo tar xjf gcc-arm-none-eabi-YOUR-VERSION.bz2 -C /usr/share/

Create links so that binaries are accessible system-wide:

sudo ln -s /usr/share/gcc-arm-none-eabi-YOUR-VERSION/bin/arm-none-eabi-gcc /usr/bin/arm-none-eabi-gcc 
sudo ln -s /usr/share/gcc-arm-none-eabi-YOUR-VERSION/bin/arm-none-eabi-g++ /usr/bin/arm-none-eabi-g++
sudo ln -s /usr/share/gcc-arm-none-eabi-YOUR-VERSION/bin/arm-none-eabi-gdb /usr/bin/arm-none-eabi-gdb
sudo ln -s /usr/share/gcc-arm-none-eabi-YOUR-VERSION/bin/arm-none-eabi-size /usr/bin/arm-none-eabi-size
sudo ln -s /usr/share/gcc-arm-none-eabi-YOUR-VERSION/bin/arm-none-eabi-objcopy /usr/bin/arm-none-eabi-objcopy

Install dependencies. ARM's "full installation instructions" listed in readme.txt won't tell you what dependencies are - you have to figure it out by trial and error. In my system I had to manually create symbolic links to force it to work:

sudo apt install libncurses-dev
sudo ln -s /usr/lib/x86_64-linux-gnu/libncurses.so.6 /usr/lib/x86_64-linux-gnu/libncurses.so.5
sudo ln -s /usr/lib/x86_64-linux-gnu/libtinfo.so.6 /usr/lib/x86_64-linux-gnu/libtinfo.so.5

Check if it works:

arm-none-eabi-gcc --version
arm-none-eabi-g++ --version
arm-none-eabi-gdb --version
arm-none-eabi-size --version

On Debian and derivatives, the package you’re looking for is gcc-arm-none-eabi:

apt install gcc-arm-none-eabi

To find this out yourself in future, install apt-file, update your indexes and use it to search for commands:

apt install apt-file
apt-file update
apt-file search bin/arm-none-eabi-gcc

I got it working on Kubuntu 19.10 installing:

apt install libncurses5

Not installing the "-dev", development or ":i386", 32-bit versions of the library.