Since you've found that
dpkg-reconfigure tzdata works, why don't you use it?
If the problem is that it's interactive and you want to script the change, it's possible. The timezone is configured through debconf. You can set values with
debconf-set-selections. Then reconfigure the package, telling it not to prompt for anything.
tzdata tzdata/Areas select Europe
tzdata tzdata/Areas seen true
tzdata tzdata/Zones/Europe select Paris
tzdata tzdata/Zones/Europe seen true
dpkg-reconfigure -fnoninteractive tzdata
/etc/localtime when they first need the time zone information. This is performed by the system's standard library, so you won't find many exceptions if at all.
/etc/localtime is usually a symbolic link to a file under
/usr/share/zoneinfo, or a copy of such a file. Most applications need to be restarted for a change of this file to take effect.
/etc/timezone contains the name of a time zone. Normally
/etc/localtime is a link to or copy of
/etc/timezone is used by the packaging system mainly (only?), which explains why changing it didn't have any visible effect.
Remember that you can use a different timezone in a particular application by starting it with the
TZ environment variable, e.g.