Segue o link do blog do eustaquiorangel de como resolver o problema:

http://eustaquiorangel.com/blog/show/308

No Debian resolvi o problema usando os comandos:

# apt-get install tz-brasil
# pecl install timezonedb

Não esquecer de colocar no php.ini a linha extension=timezonedb.so .