This is indeed planned for PHP 6, where there is an experimental function "date_format_locale()" already—but that is bound to change.

date_format / DateTime::format can't be changed to use locales, because that would break a lot of programs.

A new function date_format_locale / DateTime::formatLocale would be an excellent addition. 

I use this as a workaround now:

<?php
function date_format_locale(DateTime $dt, $format)
{
	$len = strlen($format);
	if (strcspn($format, 'DlFM') >= $len) {
		return $dt->format($format);
	}
	$marker = "\x0B";
	$keys = array('D' => '%a', 'l' => '%A', 'F' => '%B', 'M' => '%b');
	$start = 0;
	while (($start += strcspn($format, 'DlFM\\', $start)) < $len) {
		$char = $format[$start];
		if ('\\' === $char) {
			$start += 2;
		} else {
			$format[$start++] = $marker;
			$replacements[] = $keys[$char];
		}
	}
	if (!isset($replacements)) {
		return $dt->format($format);
	}
	list($wday, $month) = explode(' ', $dt->format('w n'));
	$wday = (int) $wday;
	$month = (int) $month;
	$sundays = array(0, 2, 6, 6, 3, 1, 5, 3, 7, 4, 2, 6, 4);
	$day = $sundays[$month] + $wday;
	$ts = gmmktime($hour=0, $minute=0, $second=0, $month, $day, $year=2011);
	$replacements = explode($marker, gmstrftime(implode($marker, $replacements), $ts));
	$ret = $dt->format($format);
	while (false !== $i = strpos($ret, $marker)) {
		$str = array_shift($replacements);
		//$str = mb_convert_case($str, MB_CASE_TITLE);
		$ret = substr_replace($ret, $str, $i, 1);
	}
	return $ret;
}
?>

Hope this helps, best regards!

This issue is by now more than 7 years old and targets an unsupported version of PHP.

Using a supported version of PHP you can do this via:

$date = new DateTime('2009-07-07 13:20:12');
$formatter = new IntlDateFormatter(
    'de-DE',
    IntlDateFormatter::FULL, 
    IntlDateFormatter::FULL, 
    $date->getTimezone(), 
    IntlDateFormatter::GREGORIAN, 
    'EEEE'
);
echo $formatter->format($date);

I'm therefore closing this as fixed.