Você deve conseguir fazer isso na maioria dos casos, sim. Os únicos problemas que posso ver além do problema da biblioteca que você mencionou seriam os locais de arquivo específicos da distribuição, e isso afetaria muito a sua aplicação.
Gostaria de saber se posso compilar a aplicação em uma distribuição Linux e usá-la em outra distribuição Linux (mesma arquitetura da CPU). Se não, quais problemas eu posso encontrar? Apenas os problemas que me vieram à mente são referentes a bibliotecas vinculadas dinamicamente:
Existem outras possíveis dificuldades?
Você deve conseguir fazer isso na maioria dos casos, sim. Os únicos problemas que posso ver além do problema da biblioteca que você mencionou seriam os locais de arquivo específicos da distribuição, e isso afetaria muito a sua aplicação.
Você pode facilmente executar um aplicativo compilado em cada distro que é a mesma arquitetura, se você compilá-lo estaticamente.
Se você compilá-lo dinamicamente, você se depararia com problemas como o que você mencionou (libs ausentes) ou mais frequentemente, a versão das libs de outras distros seria incompatível.