This is a really nasty problem. If there is no newer compatible version of PHP, and since updating the internal extensions did not help, I think you need to compile PHP with a custom version of ICU:
Here you can check ICU versions: http://source.icu-project.org/repos/icu/icu/tags/
Check out cd source ./configure
Now that the ICU is built, you need to run the PHP "configure" script and point it to the build directory:
./configure ... --enable-intl --with-icu-dir=/path/to/icu/build
source share