Just in case this helps: I had a similar problem with the Termux distribution on my phone. It was resolved by manually running mktexlsr which in your case would be sudo mktexlsr.
This should be done by the package post-installation routine, but maybe it is not.
The difference is highly unlikely to be related to the operating system, or differences in the tex binary. One system probably has an older tex system, and so will be using different TeX macros for some functions.
Add \listfiles to your preamble and compare the version numbers in the list that this adds at the end of the log.
Generally it is better to ...
It turned out that the installation of textlive-full was interrupted and the file /usr/share/texlive/texmf-dist/tex/latex/classicthesis was missing . The problem was solved after running sudo apt --fix-broken install.
As mentioned in the comments, installing the package texlive-publishers will enable this (no need to install texlive-full)