I've tested this using two virtual machines running Lubutu.

On the first I Installed a couple of programmes (VIM and cowsay) then ran :

sudo apt-get update
sudo apt-get upgrade
sudo dpkg --get-selections > /home/klak/my_package_list.txt

Here's what my_package_list.txt looks like

Then I booted into another VM that was a clone of the previous one prior to the VIM and cowsay installs and ran the following :

sudo apt-get update
sudo apt-get upgrade
sudo apt-get install dselect
sudo apt-get dselect update

sudo dpkg --set-selections < ./my_package_list.txt && sudo apt-get -u dselect-upgrade

However I would now expect to be able to load VIM or use cowsay, but I get :

klak@klakBox:/media/share$ vim
The program 'vim' can be found in the following packages:
 * vim
 * vim-gnome
 * vim-tiny
 * vim-athena
 * vim-gtk
 * vim-nox
Try: sudo apt-get install <selected package>
klak@klakBox:/media/share$ cowsay "boo"
The program 'cowsay' is currently not installed. You can install it by typing:
sudo apt-get install cowsay

It went through a load of install process when I ran the the above commands, so I'm not sure why this hasn't worked.

Cheers!

Edit 1

Not sure why this errors (it seems to be a valid dselect option) :

klak@klakBox:/media/share$ sudo apt-get dselect update
E: Invalid operation dselect
klak@klakBox:/media/share$ 

Edit 1.1

There's a CLI menu for dselect if I just enter sudo dselect, I'm not sure how I would include this into a script though.
From this menu I have chosen update (as the previous attempt to update failed)

• Note -> the first time I ran sudo dselect update was from a python script using os.system("sudo dselect update") -> Perhaps this errored silently, I don't know.

Edit 2

I have used the following (taken from here)

dpkg --set-selections < selections.txt

$ sudo apt-get install dselect
$ sudo dselect 
   -> Update
   -> Install

The update and install for dselect are from within a CLI menu :

• I'm not sure how to script this

• I'm not sure If I should start another question, or whether this is really a satisfactory solution to the original problem?

Thanks.

Edit 3

Here is the apt history that I've been asked for :

Start-Date: 2014-12-27  15:47:18
Commandline: apt-get upgrade
Upgrade: bind9-host:amd64 (9.9.5.dfsg-4.3, 9.9.5.dfsg-4.3ubuntu0.1), liblwres90:amd64 (9.9.5.dfsg-4.3, 9.9.5.dfsg-4.3ubuntu0.1), libsystemd-login0:amd64 (208-8ubuntu8, 208-8ubuntu8.1), libgnutls-openssl27:amd64 (3.2.16-1ubuntu2, 3.2.16-1ubuntu2.1), ppp:amd64 (2.4.5-5.1ubuntu3, 2.4.5-5.1ubuntu3.1), multiarch-support:amd64 (2.19-10ubuntu2, 2.19-10ubuntu2.1), libdns100:amd64 (9.9.5.dfsg-4.3, 9.9.5.dfsg-4.3ubuntu0.1), oxideqt-codecs-extra:amd64 (1.2.5-0ubuntu1, 1.3.4-0ubuntu0.14.10.1), libisccfg90:amd64 (9.9.5.dfsg-4.3, 9.9.5.dfsg-4.3ubuntu0.1), python3-cupshelpers:amd64 (1.5.1+20141010-0ubuntu2, 1.5.1+20141010-0ubuntu2.1), libbind9-90:amd64 (9.9.5.dfsg-4.3, 9.9.5.dfsg-4.3ubuntu0.1), tcpdump:amd64 (4.6.2-1ubuntu1, 4.6.2-1ubuntu1.1), dbus:amd64 (1.8.8-1ubuntu2, 1.8.8-1ubuntu2.1), libgnutls-deb0-28:amd64 (3.2.16-1ubuntu2, 3.2.16-1ubuntu2.1), firefox-locale-en:amd64 (33.0+build2-0ubuntu0.14.10.1, 34.0+build2-0ubuntu0.14.10.2), whoopsie:amd64 (0.2.39, 0.2.39ubuntu0.1), dkms:amd64 (2.2.0.3-1.1ubuntu5, 2.2.0.3-1.1ubuntu5.14.10), gir1.2-gtk-3.0:amd64 (3.12.2-0ubuntu15, 3.12.2-0ubuntu15.1), firefox:amd64 (33.0+build2-0ubuntu0.14.10.1, 34.0+build2-0ubuntu0.14.10.2), libsystemd-daemon0:amd64 (208-8ubuntu8, 208-8ubuntu8.1), libgudev-1.0-0:amd64 (208-8ubuntu8, 208-8ubuntu8.1), libc-dev-bin:amd64 (2.19-10ubuntu2, 2.19-10ubuntu2.1), chromium-codecs-ffmpeg-extra:amd64 (37.0.2062.94-0ubuntu1~pkg1065, 39.0.2171.65-0ubuntu0.14.10.1.1106), mountall:amd64 (2.54build1, 2.54ubuntu0.14.10.1), libpam-systemd:amd64 (208-8ubuntu8, 208-8ubuntu8.1), libc-bin:amd64 (2.19-10ubuntu2, 2.19-10ubuntu2.1), libc6:amd64 (2.19-10ubuntu2, 2.19-10ubuntu2.1), libglib2.0-0:amd64 (2.42.0-2, 2.42.1-1~ubuntu1), xserver-xorg-core:amd64 (1.16.0-1ubuntu1, 1.16.0-1ubuntu1.2), flashplugin-installer:amd64 (11.2.202.411ubuntu1, 11.2.202.425ubuntu0.14.10.1), libgtk-3-bin:amd64 (3.12.2-0ubuntu15, 3.12.2-0ubuntu15.1), dnsutils:amd64 (9.9.5.dfsg-4.3, 9.9.5.dfsg-4.3ubuntu0.1), libdbus-1-3:amd64 (1.8.8-1ubuntu2, 1.8.8-1ubuntu2.1), udev:amd64 (208-8ubuntu8, 208-8ubuntu8.1), system-config-printer-common:amd64 (1.5.1+20141010-0ubuntu2, 1.5.1+20141010-0ubuntu2.1), xserver-common:amd64 (1.16.0-1ubuntu1, 1.16.0-1ubuntu1.2), libglib2.0-data:amd64 (2.42.0-2, 2.42.1-1~ubuntu1), libflac8:amd64 (1.3.0-2, 1.3.0-2ubuntu0.14.10.1), gir1.2-gudev-1.0:amd64 (208-8ubuntu8, 208-8ubuntu8.1), libwhoopsie0:amd64 (0.2.39, 0.2.39ubuntu0.1), libappindicator3-1:amd64 (12.10.1+13.10.20130920-0ubuntu4, 12.10.1+13.10.20130920-0ubuntu4.2), ntp:amd64 (4.2.6.p5+dfsg-3ubuntu2, 4.2.6.p5+dfsg-3ubuntu2.14.10.1), libudev1:amd64 (208-8ubuntu8, 208-8ubuntu8.1), language-pack-gnome-en:amd64 (14.10+20141020, 14.10+20141205), xserver-xorg-video-intel:amd64 (2.99.914-1~exp1ubuntu4, 2.99.914-1~exp1ubuntu4.1), libgtk-3-0:amd64 (3.12.2-0ubuntu15, 3.12.2-0ubuntu15.1), libjasper1:amd64 (1.900.1-debian1-2, 1.900.1-debian1-2ubuntu0.1), libsystemd-journal0:amd64 (208-8ubuntu8, 208-8ubuntu8.1), systemd:amd64 (208-8ubuntu8, 208-8ubuntu8.1), libcurl3:amd64 (7.37.1-1ubuntu3, 7.37.1-1ubuntu3.1), libgtk-3-common:amd64 (3.12.2-0ubuntu15, 3.12.2-0ubuntu15.1), system-config-printer-gnome:amd64 (1.5.1+20141010-0ubuntu2, 1.5.1+20141010-0ubuntu2.1), dbus-x11:amd64 (1.8.8-1ubuntu2, 1.8.8-1ubuntu2.1), language-pack-en-base:amd64 (14.10+20141020, 14.10+20141205), libglib2.0-bin:amd64 (2.42.0-2, 2.42.1-1~ubuntu1), language-pack-gnome-en-base:amd64 (14.10+20141020, 14.10+20141205), linux-libc-dev:amd64 (3.16.0-24.32, 3.16.0-28.38), language-pack-en:amd64 (14.10+20141020, 14.10+20141205), libisccc90:amd64 (9.9.5.dfsg-4.3, 9.9.5.dfsg-4.3ubuntu0.1), libc6-dev:amd64 (2.19-10ubuntu2, 2.19-10ubuntu2.1), libisc95:amd64 (9.9.5.dfsg-4.3, 9.9.5.dfsg-4.3ubuntu0.1), libcurl3-gnutls:amd64 (7.37.1-1ubuntu3, 7.37.1-1ubuntu3.1), ntpdate:amd64 (4.2.6.p5+dfsg-3ubuntu2, 4.2.6.p5+dfsg-3ubuntu2.14.10.1)
End-Date: 2014-12-27  15:48:51

Start-Date: 2014-12-27  15:48:53
Commandline: apt-get install dselect
Install: dselect:amd64 (1.17.13ubuntu1)
End-Date: 2014-12-27  15:48:55

Start-Date: 2014-12-27  15:50:59
Commandline: /usr/bin/apt-get -f -oDir::State::status=/var/lib/dpkg/status -oDPkg::Options::=--admindir=/var/lib/dpkg dselect-upgrade
Install: linux-headers-3.16.0-28:amd64 (3.16.0-28.38, automatic), linux-image-3.16.0-28-generic:amd64 (3.16.0-28.38, automatic), linux-headers-3.16.0-28-generic:amd64 (3.16.0-28.38, automatic), linux-image-extra-3.16.0-28-generic:amd64 (3.16.0-28.38, automatic)
Upgrade: linux-headers-generic:amd64 (3.16.0.23.24, 3.16.0.28.29), linux-image-generic:amd64 (3.16.0.23.24, 3.16.0.28.29), linux-generic:amd64 (3.16.0.23.24, 3.16.0.28.29)
End-Date: 2014-12-27  15:52:26

The above history was from running the following commands (within python script):

import os

# This part is for reinstalling. 
os.system("sudo apt-get update")
os.system("sudo apt-get upgrade")
os.system("sudo apt-get install dselect")
#os.system("sudo dselect update")

os.system("sudo dpkg --set-selections < ./my_package_list.txt")
os.system("sudo dselect update")
os.system("sudo dselect install")

Edit 4

This is the python script that works :

 os.system("sudo apt-get install dselect")
 os.system("sudo dselect update")
 os.system("sudo dpkg --set-selections < my_package_list.txt")
 os.system("sudo apt-get -y update")
 os.system("sudo apt-get dselect-upgrade")

Obviously prior to this being run there need to have been a package list created called my_package_list.txt, and it needs to be in the same directory as the Python file.