Date::Simple (3.02) works for me (on Linux):

use strict;
use warnings;
use Date::Simple qw(date);
my $d = date("2008-01-01");
my $yesterday = $d - 1;
print $yesterday;
__END__
2007-12-31
[download]

Check the test reports and consider filing a bug report if the latest version doesn't work for you.