After doing all what you guys said:
sudo apt-get install -f
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
libopenal1 libfreebob0 fglrx-kernel-source libxml++2.6-2
kdebase-runtime-data-common libqt4-phonon nspluginwrapper libxklavier15
libdmraid1.0.0.rc15 libdmraid1.0.0.rc16 libicu40 latex-xft-fonts wine-gecko
libpolkit-qt0 libsvga1 libknotificationitem1 libcompress-bzip2-perl
libgupnp-1.0-2 xulrunner-1.9.1-gnome-support libboost-program-options1.38.0
libdns53 libindicate-gtk1 gnome-blackjack libiso9660-5 libass3 libexiv2-5
librasqal1 libisccc50 khelpcenter4 kpartx liblzma0 libpt2.6.4-plugins
libindicate3 sdparm libx264-67 python-gtksourceview kde-icons-oxygen
python-nautilusburn liblwres50 mplayer-skins libcelt0 raptor-utils
python-sip4 xulrunner-1.9.1 libntfs-3g54 libbind9-50 liblzo2-2 libffado1
libgdata5 libpt2.6.4 libisccfg50 redland-utils libpq5
firefox-3.5-gnome-support dmraid libisc50 libopenjpeg2 fxload
kdebase-runtime-bin-kde4 libgssdp-1.0-1 libfaad0
Use 'apt-get autoremove' to remove them.
The following extra packages will be installed:
The following NEW packages will be installed
0 upgraded, 1 newly installed, 0 to remove and 6 not upgraded.
3 not fully installed or removed.
Need to get 29.2MB of archives.
After this operation, 100MB of additional disk space will be used.
Do you want to continue [Y/n]? y
Get: 1 http://gb.archive.ubuntu.com/ubuntu/ lucid/restricted fglrx 2:8.723.1-0ubuntu3 [29.2MB]
Fetched 29.2MB in 1min 22s (356kB/s)
(Reading database ... 307279 files and directories currently installed.)
Unpacking fglrx (from .../fglrx_2%3a8.723.1-0ubuntu3_amd64.deb) ...
[Warning] Uninstall : inst_path_default or inst_path_override
does not exist in /etc/ati. This suggests that the ATI driver
is not installed, the ATI driver is only partially installed,
or the current ATI driver installed is an older version than the
one this script was designed for. Both files listed above are
required for determining where installed files are located.
To force uninstallation of the driver by guessing where the
uninstallation files are located, set the FORCE_ATI_UNINSTALL
environment variable and re-run /usr/share/ati/fglrx-uninstall.sh (this is not recommended).
dpkg: error processing /var/cache/apt/archives/fglrx_2%3a8.723.1-0ubuntu3_amd64.deb (--unpack):
subprocess new pre-installation script returned error exit status 1
Errors were encountered while processing:
E: Sub-process /usr/bin/dpkg returned an error code (1)
I did leoquant's lines first, then all dino99.