Написано об этом много, подробно и разнообразно. Суть проблемы заключается в том, что функция strftime PHP при выводе месяца на русском языке обычно выводит его сокращенное название и с заглавной буквы. Как правило, хотелось бы чтобы при выводе длинной даты месяц выводился все-таки в родительном падеже. Как правило предлагается сделать массив месяцев и не парится с локалью. Но вот если проект большой и во многих местах встречается стандартное преобразование - то такой подход по меньшей мере некрасивый, поскольку будет требовать заменить все вызовы стандартной функции на самописный костыль. Вместе с тем, Линукс позволяет скорректировать это как правило довольно легко. Для этого во-первых, нам надо убедиться что установлена стандартная русская локаль а не английская или C.

Проверяем:
#locale -a | grep ru
ru_RU.cp1251
ru_RU.utf8

В нашем случае есть обе и "старая" локаль и юникодовская локаль. Иногда нужно поддерживать и cp1251 локаль. Если ее нет в этом  списке, то ее нужно создать
# cd /usr/share/i18n/charmaps/
# ls | grep 1251
CP1251.gz

Ура, локаль есть ее нужно только определить.

# localedef -i ru_RU -f CP1251 ru_RU.CP1251

Собственно после этого локаль уже долна появиться. Можно ее создать альтернативно, через dpkg
# dpkg-reconfigure locales

Кажется, после этого изменения уже будут работать - ан нет. Месяц отображается с большой буквы и в именительном падеже. А все дело в том, что в линуксе есть файл, который определяет, как будут отображаться месяцы, и это... файл /usr/share/i18n/locales/ru_RU
Находим в том файле секцию, отвечающую за названия месяцев. Она называется mon и идет после abday. Здесь в страшном виде написаны месяцы с января до декабря включительно. Нужно просто поменять первые буквы и окончания слов, чтобы все было правильно. Коды букв можно найти в /usr/share/i18n/charmaps/CP1251.gz Для тех, кто не хочет этим заниматься, просто привожу фрагмент файла.

abday   "<U0412><U0441><U043A>";/
"<U041F><U043D><U0434>";/
"<U0412><U0442><U0440>";/
"<U0421><U0440><U0434>";/
"<U0427><U0442><U0432>";/
"<U041F><U0442><U043D>";/
"<U0421><U0431><U0442>"
mon     "<U044F><U043D><U0432><U0430><U0440><U044F>";/
"<U0444><U0435><U0432><U0440><U0430><U043B><U044F>";/
"<U043C><U0430><U0440><U0442><U0430>";/
"<U0430><U043F><U0440><U0435><U043B><U044F>";/
"<U043C><U0430><U044F>";/
"<U0438><U044E><U043D><U044F>";/
"<U0438><U044E><U043B><U044F>";/
"<U0430><U0432><U0433><U0443><U0441><U0442><U0430>";/
"<U0441><U0435><U043D><U0442><U044F><U0431><U0440><U044F>";/
"<U043E><U043A><U0442><U044F><U0431><U0440><U044F>";/
"<U043D><U043E><U044F><U0431><U0440><U044F>";/
"<U0434><U0435><U043A><U0430><U0431><U0440><U044F>"
abmon   "<U042F><U043D><U0432>";/

Изменения выделены жирным и цветом. Сохраняем файл и делаем еще 2 вещи. Первая: пересобираем локаль:
# locale-gen

И при необходимости перезапускаем сервис Апача
# service apache2 restart

Надеюсь, после всего этого мы имеем долгожданное счастье.
Напоследок кусок PHP скрипта, чтобы проверить как отображаются месяцы сейчас

for ($i=1;$i<=12;$i++){
$tm=strtotime($i."/1/10");
setlocale (LC_TIME, 'ru_RU.cp1251');
echo strftime("%d %B %Y",$tm)."\n";
}