IcuCollation's 'first-letters' cache key should include the version of ICU and possibly PHP that was used to build the data. Otherwise upgrading anything requires you to manually clear the caches.
I encountered this on Labs when preparing a test wiki for bug 54168 – it was set up under HHVM, then I switched to PHP 5.5 because page import doesn't work with HHVM (bug 66023), and then category listings got weird (http://i.imgur.com/Po94jiq.png for http://estonia.wmflabs.org/wiki/Kategooria:Test).
(The data is incompatible between different ICU versions, that's why we generate it dynamically in IcuCollation::getFirstLetterData() and cache instead of storing it in a static file somewhere.)
This is probably a blocker to the Trusty migration? Should be simple to fix.