You are probably using a windows machine which has different language codes in PHP than a Unix based one.
Try:
setlocale(LC_TIME, 'de_DE', 'deu_deu');
This will first try to set it to 'de_DE'
(Linux/Unix) and have the 'deu_deu'
code as a fallback for windows (PHP Version >= 4.3).