Is there a distribution that supports rolling back updated packages?

NixOS supports upgrade rollbacks, although as I understand it, it doesn't go quite as far as you'd like: if you upgrade A, B and C in one operation, you can roll that entire operation back, but not just A and B. (You should be able to roll A, B and C back, and then upgrade C...) That makes sense from a transactional perspective though.

Debian (in combination with the snapshot archive if you no longer have the old packages) will allow you to downgrade B, and tools like apt or aptitude will in many cases figure out that A also needs to be downgraded (once you've convinced them that you don't want to simply upgrade B). But as you say that tends to be somewhat messy, and package downgrades are unsupported in Debian anyway (which means that most of the time they work, but if they break it's not a bug).

On any yum based distribution (e.g. Red Hat EL, CentOS, etc), you can:

1. examine the history of changes to system using sudo yum history list

   Loaded plugins: fastestmirror
   ID     | Login user               | Date and time    | Action(s)      | Altered
   ------------------------------------------------------------------------------
       10 | Administrator <admin>    | 2016-03-08 09:08 | Install        |   11   
        9 | Administrator <admin>    | 2016-03-03 16:48 | Install        |    1   
        8 | Administrator <admin>    | 2016-03-03 16:09 | Install        |    5   
        7 | Administrator <admin>    | 2016-02-26 18:13 | Install        |    1   
        6 | Administrator <admin>    | 2016-02-26 15:12 | Install        |   27   
        5 | Administrator <admin>    | 2016-02-26 15:07 | Install        |    1   
        4 | Administrator <admin>    | 2016-02-26 15:05 | Install        |    3  <
        3 | Administrator <admin>    | 2016-02-26 15:03 | Install        |    1 > 
        2 | Administrator <admin>    | 2016-02-26 15:01 | I, U           |   49   
        1 | System <unset>           | 2016-02-26 14:38 | Install        |  296   
   history list
   

2. check the details, using sudo yum history info 10

3. rollback to a previous point in the history, using sudo yum history rollback 9

Warning

There are some obvious caveats:

1. If the old package isn't available anymore, you are toast (to quote @vonbrand),
2. If you install anything outside yum, you could break the history.

In my example, that < in the row with ID 4 (in the last column), means I cannot rollback past that point.

sudo yum history rollback 2
Loaded plugins: fastestmirror
Transaction history is incomplete, before 4.
 You can use 'history rollback force', to try anyway.
Error: Failed history rollback, incomplete

On OpenSUSE you can easily use Snapper with the Btrfs filesystem.

If you use the standard file-system configuration during installation, it is enabled by default.

Once Snapper is enabled, it is fully integrated with yast2 and zypper. It will create a filesystem snapshot every time you'd install or upgrade something (or create an user, etc).

To rollback the system to a previous condition, you have only to run yast2 snapper.