I've attached proposed changes to reflect past Altai/Tomsk time zone shifts;
the changes appear below with mangled tabs.
Thanks to Tobias Conradi for providing information.

        --ado

diff -r -c old/europe new/europe
*** old/europe    2012-05-02 17:54:22.581472200 -0400
--- new/europe    2012-05-02 18:10:54.852205400 -0400
***************
*** 1,5 ****
  # <pre>
! # @(#)europe    8.41
  # This file is in the public domain, so clarified as of
  # 2009-05-17 by Arthur David Olson.
 
--- 1,5 ----
  # <pre>
! # @(#)europe    8.42
  # This file is in the public domain, so clarified as of
  # 2009-05-17 by Arthur David Olson.
 
***************
*** 2164,2182 ****
               4:00    Russia    SVE%sT    1992 Jan 19 2:00s
               5:00    Russia    YEK%sT    2011 Mar 27 2:00s
               6:00    -    YEKT    # Yekaterinburg Time
! #
! # From Oscar van Vlijmen (2001-08-25): [This region consists of]
! # Respublika Altaj, Altajskij kraj, Omskaya oblast'.
  Zone Asia/Omsk         4:53:36 -    LMT    1919 Nov 14
               5:00    -    OMST    1930 Jun 21 # Omsk TIme
               6:00    Russia    OMS%sT    1991 Mar 31 2:00s
               5:00    Russia    OMS%sT    1992 Jan 19 2:00s
               6:00    Russia    OMS%sT    2011 Mar 27 2:00s
               7:00    -    OMST
! #
! # From Paul Eggert (2006-08-19): I'm guessing about Tomsk here; it's
! # not clear when it switched from +7 to +6.
! # Novosibirskaya oblast', Tomskaya oblast'.
  Zone Asia/Novosibirsk     5:31:40 -    LMT    1919 Dec 14 6:00
               6:00    -    NOVT    1930 Jun 21 # Novosibirsk Time
               7:00    Russia    NOV%sT    1991 Mar 31 2:00s
--- 2164,2196 ----
               4:00    Russia    SVE%sT    1992 Jan 19 2:00s
               5:00    Russia    YEK%sT    2011 Mar 27 2:00s
               6:00    -    YEKT    # Yekaterinburg Time
!
! # From Tobias Conradi (2011-09-17):
! # I know that Wikipedia is not reliable, still I would like to start with:
! # <a href="http://ru.wikipedia.org/wiki/%D0%A7%D0%B0%D1%81%D0%BE%D0%B2%D1%8B%D0%B5_%D0%BF%D0%BE%D1%8F%D1%81%D0%B0_%D0%A0%D0%BE%D1%81%D1%81%D0%B8%D0%B8#.D0.92_.D0.A0.D0.BE.D1.81.D1.81.D0.B8.D0.B9.D1.81.D0.BA.D0.BE.D0.B9_.D0.A4.D0.B5.D0.B4.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8">
! # http://ru.wikipedia.org/wiki/%D0%A7%D0%B0%D1%81%D0%BE%D0%B2%D1%8B%D0%B5_%D0%BF%D0%BE%D1%8F%D1%81%D0%B0_%D0%A0%D0%BE%D1%81%D1%81%D0%B8%D0%B8#.D0.92_.D0.A0.D0.BE.D1.81.D1.81.D0.B8.D0.B9.D1.81.D0.BA.D0.BE.D0.B9_.D0.A4.D0.B5.D0.B4.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8
! # </a>
!
! # From Arthur David Olson (2012-05-02):
! # According to
! # <a href="http://translate.google.com/translate?hl=en&sl=ru&u=http://ru.wikipedia.org/wiki/%25D0%25A7%25D0%25B0%25D1%2581%25D0%25BE%25D0%25B2%25D1%258B%25D0%25B5_%25D0%25BF%25D0%25BE%25D1%258F%25D1%2581%25D0%25B0_%25D0%25A0%25D0%25BE%25D1%2581%25D1%2581%25D0%25B8%25D0%25B8&ei=DqChT_OqMNT0gAe3ktH4CA&sa=X&oi=translate&ct=result&resnum=1&ved=0CCYQ7gEwAA&prev=/search%3Fq%3Dhttp://ru.wikipedia.org/wiki/%2525D0%2525A7%2525D0%2525B0%2525D1%252581%2525D0%2525BE%2525D0%2525B2%2525D1%25258B%2525D0%2525B5_%2525D0%2525BF%2525D0%2525BE%2525D1%25258F%2525D1%252581%2525D0%2525B0_%2525D0%2525A0%2525D0%2525BE%2525D1%252581%2525D1%252581%2525D0%2525B8%2525D0%2525B8%2523.D0.92_.D0.A0.D0.BE.D1.81.D1.81.D0.B8.D0.B9.D1.81.D0.BA.D0.BE.D0.B9_.D0.A4.D0.B5.D0.B4.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8%26num%3D100%26hl%3Den%26safe%3Doff%26prmd">
! # http://translate.google.com/translate?hl=en&sl=ru&u=http://ru.wikipedia.org/wiki/%25D0%25A7%25D0%25B0%25D1%2581%25D0%25BE%25D0%25B2%25D1%258B%25D0%25B5_%25D0%25BF%25D0%25BE%25D1%258F%25D1%2581%25D0%25B0_%25D0%25A0%25D0%25BE%25D1%2581%25D1%2581%25D0%25B8%25D0%25B8&ei=DqChT_OqMNT0gAe3ktH4CA&sa=X&oi=translate&ct=result&resnum=1&ved=0CCYQ7gEwAA&prev=/search%3Fq%3Dhttp://ru.wikipedia.org/wiki/%2525D0%2525A7%2525D0%2525B0%2525D1%252581%2525D0%2525BE%2525D0%2525B2%2525D1%25258B%2525D0%2525B5_%2525D0%2525BF%2525D0%2525BE%2525D1%25258F%2525D1%252581%2525D0%2525B0_%2525D0%2525A0%2525D0%2525BE%2525D1%252581%2525D1%252581%2525D0%2525B8%2525D0%2525B8%2523.D0.92_.D0.A0.D0.BE.D1.81.D1.81.D0.B8.D0.B9.D1.81.D0.BA.D0.BE.D0.B9_.D0.A4.D0.B5.D0.B4.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8%26num%3D100%26hl%3Den%26safe%3Doff%26prmd
! # </a>: "...the regions of Western Siberia,
! # formerly stationed in the area of MSK+4,
! # switched to the time of MSK+3, joining the Omsk Time:
! # Novosibirsk Region May 23, 1993 at 00:00,
! # Altai and the Altai Republic May 28, 1995 at 4:00 am,
! # Tomsk Region May 1, 2002 at 3:00 am."
!
! # Omskaya oblast'.
  Zone Asia/Omsk         4:53:36 -    LMT    1919 Nov 14
               5:00    -    OMST    1930 Jun 21 # Omsk TIme
               6:00    Russia    OMS%sT    1991 Mar 31 2:00s
               5:00    Russia    OMS%sT    1992 Jan 19 2:00s
               6:00    Russia    OMS%sT    2011 Mar 27 2:00s
               7:00    -    OMST
!
! # Novosibirskaya oblast'.
  Zone Asia/Novosibirsk     5:31:40 -    LMT    1919 Dec 14 6:00
               6:00    -    NOVT    1930 Jun 21 # Novosibirsk Time
               7:00    Russia    NOV%sT    1991 Mar 31 2:00s
***************
*** 2185,2190 ****
--- 2199,2222 ----
               6:00    Russia    NOV%sT    2011 Mar 27 2:00s
               7:00    -    NOVT
 
+ # Respublika Altaj, Altajskij kraj.
+ Zone Asia/Barnaul     5:35:00 -    LMT    1919 Nov 14
+              6:00    -    BART    1930 Jun 21 # Barnaul Time
+              7:00    Russia    BAR%sT    1991 Mar 31 2:00s
+              6:00    Russia    BAR%sT    1992 Jan 19 2:00s
+              7:00    Russia    BAR%sT    1995 May 28 4:00s # wikipedia.ru
+              6:00    Russia    OMS%sT    2011 Mar 27 2:00s
+              7:00    -    OMST
+            
+ # Tomskaya oblast'.
+ Zone Asia/Tomsk         5:39:52 -    LMT    1919 Dec 14 6:00
+              6:00    -    TOMT    1930 Jun 21 # Tomsk Time
+              7:00    Russia    TOM%sT    1991 Mar 31 2:00s
+              6:00    Russia    TOM%sT    1992 Jan 19 2:00s
+              7:00    Russia    TOM%sT    2002 May  1 3:00s # wikipedia.ru
+              6:00    Russia    OMS%sT    2011 Mar 27 2:00s
+              7:00    -    OMST
+
  # From Alexander Krivenyshev (2009-10-13):
  # Kemerovo oblast' (Kemerovo region) in Russia will change current time zone on
  # March 28, 2010:
diff -r -c old/zone.tab new/zone.tab
*** old/zone.tab    2012-05-02 17:54:34.515493100 -0400
--- new/zone.tab    2012-05-02 17:53:52.504619400 -0400
***************
*** 1,5 ****
  # <pre>
! # @(#)zone.tab    8.55
  # This file is in the public domain, so clarified as of
  # 2009-05-17 by Arthur David Olson.
  #
--- 1,5 ----
  # <pre>
! # @(#)zone.tab    8.56
  # This file is in the public domain, so clarified as of
  # 2009-05-17 by Arthur David Olson.
  #
***************
*** 338,343 ****
--- 338,345 ----
  RU    +5651+06036    Asia/Yekaterinburg    Moscow+02 - Urals
  RU    +5500+07324    Asia/Omsk    Moscow+03 - west Siberia
  RU    +5502+08255    Asia/Novosibirsk    Moscow+03 - Novosibirsk
+ RU    +5322+08345    Asia/Barnaul    Moscow+03 - Altai
+ RU    +5800+08458    Asia/Tomsk    Moscow+03 - Tomsk
  RU    +5345+08707    Asia/Novokuznetsk    Moscow+03 - Novokuznetsk
  RU    +5601+09250    Asia/Krasnoyarsk    Moscow+04 - Yenisei River
  RU    +5216+10420    Asia/Irkutsk    Moscow+05 - Lake Baikal