Failed Octave Uninstallation on Ubuntu 12.04 (Trouble Reinstalling Octave)

I'm an Ubuntu newb, so please bear with me.

On trying to uninstall octave-3.2.4, I ended up doing rm -rf on all the octave related directories and files in /usr/bin/ before I could install the latest version of GNU Octave. On trying to install Octave now, I'm getting the following error, with which I need help resolving:

The following packages have unmet dependencies:  
octave : 

Depends: libarpack2 (>= 2.1) but it is not going to be installed  
      Depends: libfftw3-3 but it is not installable  
      Depends: liboctave3 (= 4.0.0-3ubuntu2~octave~precise5) but it is   not going to be installed  
      Depends: libqscintilla2-8 but it is not installable  
      Depends: default-jre-headless but it is not installable  
      Recommends: pstoedit but it is not installable  
E: Unable to correct problems, you have held broken packages.  

My commands attempting to reinstall Octave:

wget ftp://ftp.gnu.org/gnu/octave/octave-3.8.0.tar.bz2
tar -xvf octave-3.8.0.tar.bz2
cd octave-3.8.0
sudo apt-get build-dep octave
./configure
make
sudo make install

Edit: Output of apt-cache policy libarpack2

libarpack2:
  Installed: (none)
  Candidate: 3.0.2-3
  Version table:
     3.0.2-3 0
        500 http://archive.ubuntu.com/ubuntu/ precise/universe amd64 Packages
        100 /var/lib/dpkg/status

Edit: Output of apt-cache policy libarpack2-dev

libarpack2-dev:
  Installed: (none)
  Candidate: 3.0.2-3
  Version table:
     3.0.2-3 0
        500 http://archive.ubuntu.com/ubuntu/ precise/universe amd64 Packages

Edit: I hope this is relevant for a clue. Output for sudo apt-get upgrade

Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages have been kept back:
  dpkg-dev libatlas3gf-base libblas-dev libblas3gf libdpkg-perl liblapack-dev liblapack3gf linux-headers-generic-lts-quantal
  linux-image-generic-lts-quantal r-base-dev r8168-dkms texinfo
0 upgraded, 0 newly installed, 0 to remove and 12 not upgraded.

Edit: Output of apt-cache policy libarpack2 libfftw3-3 liboctave3 libqscintilla2-8 default-jre-headless pstoedit

libarpack2:
  Installed: (none)
  Candidate: 3.0.2-3
  Version table:
     3.0.2-3 0
        500 http://archive.ubuntu.com/ubuntu/ precise/universe amd64 Packages
        100 /var/lib/dpkg/status
libfftw3-3:
  Installed: (none)
  Candidate: (none)
  Version table:
     3.3-1ubuntu1 0
        100 /var/lib/dpkg/status
liboctave3:
  Installed: (none)
  Candidate: 4.0.0-3ubuntu2~octave~precise5
  Version table:
     4.0.0-3ubuntu2~octave~precise5 0
        500 http://ppa.launchpad.net/octave/stable/ubuntu/ precise/main amd64 Packages
libqscintilla2-8:
  Installed: (none)
  Candidate: (none)
  Version table:
default-jre-headless:
  Installed: (none)
  Candidate: (none)
  Version table:
pstoedit:
  Installed: (none)
  Candidate: (none)
  Version table:

Edit: Output of sudo apt-get install libarpack2 libfftw3-3 liboctave3 libqscintilla2-8 default-jre-headless pstoedit

Reading package lists... Done
Building dependency tree       
Reading state information... Done
Package libfftw3-3 is not available, but is referred to by another package.
This may mean that the package is missing, has been obsoleted, or
is only available from another source

Package default-jre-headless is not available, but is referred to by another package.
This may mean that the package is missing, has been obsoleted, or
is only available from another source

Package pstoedit is not available, but is referred to by another package.
This may mean that the package is missing, has been obsoleted, or
is only available from another source

Package libqscintilla2-8 is not available, but is referred to by another package.
This may mean that the package is missing, has been obsoleted, or
is only available from another source

E: Package 'libfftw3-3' has no installation candidate
E: Package 'libqscintilla2-8' has no installation candidate
E: Package 'default-jre-headless' has no installation candidate
E: Package 'pstoedit' has no installation candidate

Solution 1:

All missing packages are in the main repository, therfore

sudo apt-add-repository main
sudo apt-get update

And multiverse is also a good idea

sudo apt-add-repository multiverse
sudo apt-get update

If sudo apt-add-repository main and sudo apt-add-repository multiverse doesn't work, do the following

1. sudo mv /etc/apt/sources.list /etc/apt/sources.list.bak
2. Open Software & Updates

3. Activate the entries for main, universe and multiverse

   

4. Click Close

5. Refresh the package sources via Reload

   

Remove your self-compiling adventure

cd octave-3.8.0
sudo make uninstall

Install octave again via

sudo apt-get install --reinstall octave

And please, don't "remove" packages via deleting files in /usr/bin