I experienced the same issue. I'll outline the steps I took to resolve it on Ubuntu 10.10.
1) make sure you have 'gettext' installed,
sudo apt-get install gettext
If you can't install "gettext," you can instead install "php-gettext." If you already have "gettext" installed, "php-gettext" is not necessary.
2) After that, create your language's locale. I'll use the term "sv SE" in this example. '/usr/share/i18n/SUPPORTED' contains a list of the supported locales.
less /usr/share/i18n/SUPPORTED
You'll find multiple lines that start with 'sv_SE',
sv_SE.UTF-8 UTF-8
sv_SE ISO-8859-1
sv_SE.ISO-8859-15 ISO-8859-15
This implies that you have a variety of choices for creating the locale for sv SE. The default character set for that locale is indicated by one of the parameters, sv SE ISO-8859-1, which lacks a period (.). Run the following command to create the locale for the default character set:
sudo locale-gen sv_SE
If you want to generate that locale for the UTF-8 character set, run this command,
sudo locale-gen sv_SE.UTF-8
Restart Apache after generating locales (it won't find the newly generated locales otherwise),
sudo service apache2 restart
3) update your PHP script to match the locale you generated. If you generated the locale for 'sv_SE',
setlocale(LC_ALL, "sv_SE");
But if you generated the UTF-8 equivalent of that locale, use,
setlocale(LC_ALL, "sv_SE.UTF-8");
All should work now.