Ubuntu: Cannot apt-get upgrade server, dpkg permission denied even when root

I've ran a general audit of the system and found that a few packages were aging, such as OpenSSH and related so I went to apt-get update then upgrade.

Unfortunately it seems to get the packages correctly (downloading), however cannot finish the upgrade process. Here is an exact copy of my recent command line to show this error, note that packages were already downloaded from previous test of this so it needs to retrieve zero bytes (note I am root:)

root@foobar:~# apt-get upgrade
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following packages will be upgraded:
  apt apt-utils at bind9-host binutils bsdutils curl dhcp3-client dhcp3-common
  dnsutils dpkg-dev ifupdown initscripts krb5-multidev language-pack-en
  language-pack-en-base libapache2-mod-php5 libapr1 libapr1-dev
  libavahi-client3 libavahi-common-data libavahi-common3 libbind9-60 libblkid1
  libc-bin libc-dev-bin libc6 libc6-dev libcurl3 libcurl3-gnutls libdbus-1-3
  libdns64 libgssapi-krb5-2 libgssrpc4 libisc60 libisccc60 libisccfg60
  libk5crypto3 libkadm5clnt-mit7 libkadm5srv-mit7 libkdb5-4 libkrb5-3
  libkrb5-dev libkrb5support0 liblcms1 libldap-2.4-2 libldap2-dev liblwres60
  libmysqlclient-dev libmysqlclient16 libnss3-1d libpam-runtime libpam0g
  libpango1.0-0 libpango1.0-common libplymouth2 libpq-dev libpq5 libssl-dev
  libssl0.9.8 libtiff4 libudev0 libuuid1 libxml2 libxml2-dev linux-libc-dev
  login logrotate mount mysql-client mysql-client-5.1 mysql-client-core-5.1
  mysql-common mysql-server mysql-server-5.1 mysql-server-core-5.1 nginx ntp
  ntpdate openjdk-6-jre-headless openjdk-6-jre-lib openssh-client
  openssh-server openssl opera passwd perl perl-base perl-modules php-pear
  php5 php5-cli php5-common php5-dev php5-gd php5-mysql plymouth postfix rsync
  rsyslog sudo sysv-rc sysvinit-utils tzdata tzdata-java udev update-inetd
  upstart util-linux uuid-dev vsftpd xkb-data
112 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
1 not fully installed or removed.
Need to get 0B/124MB of archives.
After this operation, 3,506kB of additional disk space will be used.
Do you want to continue [Y/n]? Y
Extracting templates from packages: 100%
Preconfiguring packages ...
/tmp/ifupdown.config.188089: 13: dpkg: Permission denied
/tmp/openssh-server.config.188701: 49: dpkg: Permission denied
Could not exec dpkg!
E: Sub-process /usr/bin/dpkg returned an error code (100)

I am completely unsure of what I have done wrong, this version is 10.04.2 LTS of Ubuntu and it is of course the server edition no of which I am using on my VPS, will it force me to do some dist-upgrade or something first? is it just some simple permission problem?

One thing I have done recently before this, I had set the sticky bit in /tmp as recommended by an auditing guide so I could not allow other users to modify other users' files in that folder (it is just a folder), I am wondering if that is it, or I need to run this in a different manner..

Ken.

As requested per below comment,

ls -la output:

root@foobar:~# ls -la /tmp
total 20
drwxr-xr-t  5 mainuser mainuser 4096 2011-07-06 03:17 .
drwxr-xr-x 23 root   root   4096 2011-07-05 04:39 ..
drwxr-xr-x  2 root   root   4096 2011-06-17 03:30 hsperfdata_root
drwxrwxrwt  2 root   root   4096 2011-06-15 03:47 .ICE-unix
-rw-------  1 root   root      0 2011-07-05 04:13 lsat1.lsat
drwxrwxrwt  2 root   root   4096 2011-06-15 03:47 .X11-unix

Update: now is this after suggestion to fix permissions:

total 20
drwxrwxrwt  5 root root 4096 2011-07-06 03:50 .
drwxr-xr-x 23 root root 4096 2011-07-05 04:39 ..
drwxr-xr-x  2 root root 4096 2011-06-17 03:30 hsperfdata_root
drwxrwxrwt  2 root root 4096 2011-06-15 03:47 .ICE-unix
-rw-------  1 root root    0 2011-07-05 04:13 lsat1.lsat
drwxrwxrwt  2 root root 4096 2011-06-15 03:47 .X11-unix

And problem still persists.