I've been having headaches with this one too. I added this and it worked:
putenv('LANGUAGE=en_US');
Next to that I use the following:
$domain = 'woohoo';
setlocale(LC_ALL, 'en_US.utf8');
putenv('LANGUAGE=en_US');
if( ENV != 'live' ){
// reset caching nocache is a simlink to "."
bindtextdomain($domain, dirname(__FILE__) . '/../locale/nocache');
}
bindtextdomain($domain, dirname(__FILE__) . '/../locale');
bind_textdomain_codeset($domain, 'UTF-8');
textdomain($domain);
Also, in my setup it only started working when I added the iso code to the .po file:
msgid ""
msgstr ""
"Language: en_US\n"