After upgrading an application to Symfony 2.3.x I stumbled across this exception just the other day.
The documentation explains in detail why this can be the case and how to solve the issue.
However, it didn't work for me although ICU 4.8.1 is installed on our server which phpinfo() clearly stated but php -i | grep ICU did not.
And this was a hint to the solution: CLI and Apache use different php.ini files thus I had to provide the correct ini when invoking composer:
php -c /path/to/php.ini composer.phar install.