In Lucid, I get the following results when checking the two time zone changes called out in this bug.  You can see that on the Sun Mar 28 switch to DST, the times do not match between Europe/Samara vs. Europe/Moscow and Asia/Kamchatka vs. Asia/Magadan:

$ apt-cache policy tzdata
tzdata:
  Installed: 2010i-1
  Candidate: 2010i-1
  Version table:
 *** 2010i-1 0
        500 http://us.archive.ubuntu.com/ubuntu/ lucid/main Packages
        100 /var/lib/dpkg/status
$ zdump -v -c 2010,2011  Europe/Moscow
Europe/Moscow  Fri Dec 13 20:45:52 1901 UTC = Fri Dec 13 23:15:52 1901 MMT isdst=0 gmtoff=9000
Europe/Moscow  Sat Dec 14 20:45:52 1901 UTC = Sat Dec 14 23:15:52 1901 MMT isdst=0 gmtoff=9000
Europe/Moscow  Sat Mar 27 22:59:59 2010 UTC = Sun Mar 28 01:59:59 2010 MSK isdst=0 gmtoff=10800
Europe/Moscow  Sat Mar 27 23:00:00 2010 UTC = Sun Mar 28 03:00:00 2010 MSD isdst=1 gmtoff=14400
Europe/Moscow  Sat Oct 30 22:59:59 2010 UTC = Sun Oct 31 02:59:59 2010 MSD isdst=1 gmtoff=14400
Europe/Moscow  Sat Oct 30 23:00:00 2010 UTC = Sun Oct 31 02:00:00 2010 MSK isdst=0 gmtoff=10800
Europe/Moscow  Mon Jan 18 03:14:07 2038 UTC = Mon Jan 18 06:14:07 2038 MSK isdst=0 gmtoff=10800
Europe/Moscow  Tue Jan 19 03:14:07 2038 UTC = Tue Jan 19 06:14:07 2038 MSK isdst=0 gmtoff=10800
$ zdump -v -c 2010,2011  Europe/Samara
Europe/Samara  Fri Dec 13 20:45:52 1901 UTC = Sat Dec 14 00:06:28 1901 LMT isdst=0 gmtoff=12036
Europe/Samara  Sat Dec 14 20:45:52 1901 UTC = Sun Dec 15 00:06:28 1901 LMT isdst=0 gmtoff=12036
Europe/Samara  Sat Mar 27 21:59:59 2010 UTC = Sun Mar 28 01:59:59 2010 SAMT isdst=0 gmtoff=14400
Europe/Samara  Sat Mar 27 22:00:00 2010 UTC = Sun Mar 28 02:00:00 2010 SAMST isdst=1 gmtoff=14400
Europe/Samara  Sat Oct 30 22:59:59 2010 UTC = Sun Oct 31 02:59:59 2010 SAMST isdst=1 gmtoff=14400
Europe/Samara  Sat Oct 30 23:00:00 2010 UTC = Sun Oct 31 02:00:00 2010 SAMT isdst=0 gmtoff=10800
Europe/Samara  Mon Jan 18 03:14:07 2038 UTC = Mon Jan 18 06:14:07 2038 SAMT isdst=0 gmtoff=10800
Europe/Samara  Tue Jan 19 03:14:07 2038 UTC = Tue Jan 19 06:14:07 2038 SAMT isdst=0 gmtoff=10800

$ zdump -v -c 2010,2011  Asia/Magadan 
Asia/Magadan  Fri Dec 13 20:45:52 1901 UTC = Sat Dec 14 06:49:04 1901 LMT isdst=0 gmtoff=36192
Asia/Magadan  Sat Dec 14 20:45:52 1901 UTC = Sun Dec 15 06:49:04 1901 LMT isdst=0 gmtoff=36192
Asia/Magadan  Sat Mar 27 14:59:59 2010 UTC = Sun Mar 28 01:59:59 2010 MAGT isdst=0 gmtoff=39600
Asia/Magadan  Sat Mar 27 15:00:00 2010 UTC = Sun Mar 28 03:00:00 2010 MAGST isdst=1 gmtoff=43200
Asia/Magadan  Sat Oct 30 14:59:59 2010 UTC = Sun Oct 31 02:59:59 2010 MAGST isdst=1 gmtoff=43200
Asia/Magadan  Sat Oct 30 15:00:00 2010 UTC = Sun Oct 31 02:00:00 2010 MAGT isdst=0 gmtoff=39600
Asia/Magadan  Mon Jan 18 03:14:07 2038 UTC = Mon Jan 18 14:14:07 2038 MAGT isdst=0 gmtoff=39600
Asia/Magadan  Tue Jan 19 03:14:07 2038 UTC = Tue Jan 19 14:14:07 2038 MAGT isdst=0 gmtoff=39600
$ zdump -v -c 2010,2011  Asia/Kamchatka
Asia/Kamchatka  Fri Dec 13 20:45:52 1901 UTC = Sat Dec 14 07:20:28 1901 LMT isdst=0 gmtoff=38076
Asia/Kamchatka  Sat Dec 14 20:45:52 1901 UTC = Sun Dec 15 07:20:28 1901 LMT isdst=0 gmtoff=38076
Asia/Kamchatka  Sat Mar 27 13:59:59 2010 UTC = Sun Mar 28 01:59:59 2010 PETT isdst=0 gmtoff=43200
Asia/Kamchatka  Sat Mar 27 14:00:00 2010 UTC = Sun Mar 28 02:00:00 2010 PETST isdst=1 gmtoff=43200
Asia/Kamchatka  Sat Oct 30 14:59:59 2010 UTC = Sun Oct 31 02:59:59 2010 PETST isdst=1 gmtoff=43200
Asia/Kamchatka  Sat Oct 30 15:00:00 2010 UTC = Sun Oct 31 02:00:00 2010 PETT isdst=0 gmtoff=39600
Asia/Kamchatka  Mon Jan 18 03:14:07 2038 UTC = Mon Jan 18 14:14:07 2038 PETT isdst=0 gmtoff=39600
Asia/Kamchatka  Tue Jan 19 03:14:07 2038 UTC = Tue Jan 19 14:14:07 2038 PETT isdst=0 gmtoff=39600