Apparently the Linux dedicated sever binary got packaged with the desktop version of steamclient.so.
This is actually pretty simple to fix. Unlike suggested in #0022379 you do not need to install the dynamic libraries the broken steamclient.so is linked against.
Instead replace it with the steamclient.so from your SteamCMD installation (look inside the linux32/-directory).
This fix will reward you with the following error messages on server startup:
> /home/buildbot/buildslave/steam_rel_client_linux/build/src/clientdll/applicationmanager.cpp (2990) : Assertion Failed: CApplicationManager::GetMountVolume: invalid index
> /home/buildbot/buildslave/steam_rel_client_linux/build/src/clientdll/applicationmanager.cpp (2990) : Assertion Failed: CApplicationManager::GetMountVolume: invalid index
> /home/buildbot/buildslave/steam_rel_client_linux/build/src/clientdll/applicationmanager.cpp (3118) : Assertion Failed: m_vecInstallBaseFolders.Count() > 0
Probably some minor(?) incompatibility, but at least clients will be able to connect again.