Is there any way to roll back the most recent upgrade?

In synaptics, you can at least control, what have been the recent updates: File-menu, history.

(if synaptic is startable, with the broken system). So with an apt-...-command, to revert their update, it shouldn't be too hard.

I guess there is a history-command for the command line too.

Maybe you have to delete the whole package, and install a specific version. Afaik, it is possible to install a specific version, but I never had the need to do so.

update: Looked up how to do with apt:

Find packages installed in the last 3x24h:

find /var/lib/dpkg/info/ -name \*.list -mtime -3 | sed 's#.list$##;s#.*/##' 

With apt-cache policy, you see available versions of a program:

sudo apt-cache policy PROGRAM:
 *** 3.6.7+build3+nobinonly-0ubuntu0.10.04.1 0
        500 http://de.archive.ubuntu.com/ubuntu/ lucid-updates/main Packages
        500 http://security.ubuntu.com/ubuntu/ lucid-security/main Packages
        100 /var/lib/dpkg/status
     3.6.3+nobinonly-0ubuntu4 0

here 3.6.7 and 3.6.3 . Now you know what earlier version might be installed (often not the immediate predecessor):

sudo apt-get install PROGRAM=3.6.3

Then you need to do an apt-pinning, to prevent future updates:

Create a new file in /etc/apt/preferences.d/ (if >= 10.4) named after your program,

Package: program
Pin: version 3.6.3*
Pin-Priority: 1000

Mostly you can consult /var/log/apt/history.log for changes done by apt/synaptic. It's just a little forensic and alot of cut/paste to do.

Go back to the date when your system was still working fine.

First take all packages that got installed since then and put them together in an uninstall script. When the script has finished, start re-adding all removed packages again.

An example case:
logfile:

Start-Date: 2014-05-28  21:28:11
Commandline: synaptic
Install: libfglrx-amdxvba1:amd64 (13.12-3kali1, automatic), libgl1-fglrx-glx:amd64 (13.12-3kali1), glx-alternative-fglrx:amd64 (0.4.1kali1, automatic), libfglrx:amd64 (13.12-3kali1, au$
Remove: fglrx-glx-ia32:amd64 (12-6+point-3)
End-Date: 2014-05-28  21:28:27

you can see,

libfglrx-amdxvba1:amd64 libgl1-fglrx-glx:amd64 glx-alternative-fglrx:amd64 & libfglrx:amd64 

got installed by Synaptic. as like libfglrx:amd64 got removed by Synaptic.

We went the reverse order, so first we remove the newly installed packages and we re-add the packages that got removed.

A working command for this case could looks like:

sudo apt-get remove -y libfglrx-amdxvba1:amd64 libgl1-fglrx-glx:amd64 glx-alternative-fglrx:amd64 libfglrx:amd64 && sudo apt-get install -y libfglrx:amd64

Maybe it wouldn't be the best idea to go without the -y switch - to have more control about the process (to avoid broken dependencies). Most of you wouldn't break their finger while do a few verification "y"

In most cases a rollback is possible this way, but if dependencies are already broken - you may run into a even bigger issue.

Most of the time if your system is broken it is a kernel problem.

Simply boot an older kernel and reinstall the most recent packages (especially kernel packages) that probably didn't update correctly. Few notes:

/var/log/dpkg.log

is your friend to check what is the list of the recently updated/installed packages

sudo apt-get -f install

can most of the time fix half-installed packages

Unfortunately there is no way to do this yet. Filesystem level snapshot/rollback is one of the features of the upcoming btrfs, but it has a ways yet to become feature complete and stable enough to use as the default filesystem.

When doing a major upgrade, I clone the disk using Clonezilla. Burn it on a CD, have a spare (external) HDD available and follow the instructions on the Clonezilla LiveCD. Choose the partition-image mode, this uses the least space.

If you think you've broken your system (or wish to revert any changes), simply boot in the Clonezilla LiveCD, select the image on your (external) HDD and restore it. As these images are a literal copy of every bit on your disk, this might take a few hours depending on your disk speed and connection speed (the connection between the data, usually an external USB HDD, and the computer).

By the way, this is called a backup method.