LoadError: Couldn't find libpython while building PyCall #1061

I get the following error when running Pkg.build("PyCall"):
ERROR: LoadError: Couldn't find libpython; check your PYTHON environment variable.

The version info:
Julia Version 1.9.2
Commit e4ee485e909 (2023-07-05 09:39 UTC)
Platform Info:
OS: Linux (x86_64-linux-gnu)
CPU: 32 × Intel(R) Xeon(R) Gold 5118 CPU @ 2.30GHz
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: libLLVM-14.0.6 (ORCJIT, skylake-avx512)
Threads: 1 on 48 virtual cores

I have noticed similar issues (#588, #565), which seemed solved in current release, so not clear what happens here.
I have libpython3.10.a at /usr/local/lib/. The python3-dev package has also been installed.
Any suggestions? Thanks a lot!

Full output messages with ENV["PYCALL_DEBUG_BUILD"] = "yes" are as follows:

julia> Pkg.build("PyCall")
Building Conda ─→ ~/.julia/scratchspaces/44cfe95a-1eb2-52ea-b672-e2afdf69b78f/8c86e48c0db1564a1d49548d3515ced5d604c408/build.log
Building PyCall → ~/.julia/scratchspaces/44cfe95a-1eb2-52ea-b672-e2afdf69b78f/43d304ac6f0354755f1d60730ece8c499980f7ba/build.log
ERROR: Error building PyCall:
DEBUG is_windows = False
DEBUG is_apple = False
DEBUG Candidate: /root/.julia/packages/PyCall/ilqDX/deps/python3
DEBUG Not found.
DEBUG Candidate: /usr/local/lib/python3.10/config-3.10-x86_64-linux-gnu/libpython3.10.a
DEBUG Found: /usr/local/lib/python3.10/config-3.10-x86_64-linux-gnu/libpython3.10.a
DEBUG Candidate: /usr/local/lib/python3.10/config-3.10-x86_64-linux-gnu/libpython3.10.so
DEBUG Not found.
DEBUG Candidate: /usr/local/lib/python3.10/config-3.10-x86_64-linux-gnu/libpython3.so
DEBUG Not found.
DEBUG Candidate: /usr/local/lib/python3.10/config-3.10-x86_64-linux-gnu/libpython.so
DEBUG Not found.
DEBUG Candidate: /usr/local/lib/libpython3.10.a
DEBUG Found: /usr/local/lib/libpython3.10.a
DEBUG Candidate: /usr/local/lib/libpython3.10.so
DEBUG Not found.
DEBUG Candidate: /usr/local/lib/libpython3.so
DEBUG Not found.
DEBUG Candidate: /usr/local/lib/libpython.so
DEBUG Not found.
DEBUG Candidate: /usr/lib/libpython3.10.a
DEBUG Not found.
DEBUG Candidate: /usr/lib/libpython3.10.so
DEBUG Not found.
DEBUG Candidate: /usr/lib/libpython3.so
DEBUG Not found.
DEBUG Candidate: /usr/lib/libpython.so
DEBUG Not found.
DEBUG Candidate: /usr/local/libpython3.10.a
DEBUG Not found.
DEBUG Candidate: /usr/local/libpython3.10.so
DEBUG Not found.
DEBUG Candidate: /usr/local/libpython3.so
DEBUG Not found.
DEBUG Candidate: /usr/local/libpython.so
DEBUG Not found.
DEBUG Candidate: None
DEBUG Not found.
DEBUG Candidate: libpython3.6m.so.1.0
DEBUG Not found.
dlopen(/usr/local/lib/python3.10/config-3.10-x86_64-linux-gnu/libpython3.10.a) ==> ErrorException("could not load library "/usr/local/lib/python3.10/config-3.10-x86_64-linux-gnu/libpython3.10.a"\n/usr/local/lib/python3.10/config-3.10-x86_64-linux-gnu/libpython3.10.a: invalid ELF header")
dlopen(/usr/local/lib/libpython3.10.a) ==> ErrorException("could not load library "/usr/local/lib/libpython3.10.a"\n/usr/local/lib/libpython3.10.a: invalid ELF header")
dlopen(libpython3.10) ==> ErrorException("could not load library "libpython3.10"\nlibpython3.10.so: cannot open shared object file: No such file or directory")
dlopen(libpython3.10) ==> ErrorException("could not load library "libpython3.10"\nlibpython3.10.so: cannot open shared object file: No such file or directory")
dlopen(libpython3) ==> ErrorException("could not load library "libpython3"\nlibpython3.so: cannot open shared object file: No such file or directory")
dlopen(libpython) ==> ErrorException("could not load library "libpython"\nlibpython.so: cannot open shared object file: No such file or directory")
ERROR: LoadError: Couldn't find libpython; check your PYTHON environment variable.

The python executable we tried was python3 (= version 3.10).
Re-building with
ENV["PYCALL_DEBUG_BUILD"] = "yes"
may provide extra information for why it failed.

Stacktrace:
[1] error(s::String)
@ Base ./error.jl:35
[2] find_libpython(python::String; _dlopen::typeof(Base.Libc.Libdl.dlopen))
@ Main ~/.julia/packages/PyCall/ilqDX/deps/buildutils.jl:72
[3] find_libpython(python::String)
@ Main ~/.julia/packages/PyCall/ilqDX/deps/buildutils.jl:40
[4] top-level scope
@ ~/.julia/packages/PyCall/ilqDX/deps/build.jl:82
[5] include(fname::String)
@ Base.MainInclude ./client.jl:478
[6] top-level scope
@ none:5
in expression starting at /root/.julia/packages/PyCall/ilqDX/deps/build.jl:43
Stacktrace:
[1] pkgerror(msg::String)
@ Pkg.Types /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/Types.jl:69
[2] (::Pkg.Operations.var"#67#74"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String})()
@ Pkg.Operations /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/Operations.jl:1153
[3] withenv(::Pkg.Operations.var"#67#74"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String}, ::Pair{String, String}, ::Vararg{Pair{String}})
@ Base ./env.jl:197
[4] (::Pkg.Operations.var"#117#122"{String, Bool, Bool, Bool, Pkg.Operations.var"#67#74"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String}, Pkg.Types.PackageSpec})()
@ Pkg.Operations /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/Operations.jl:1827
[5] with_temp_env(fn::Pkg.Operations.var"#117#122"{String, Bool, Bool, Bool, Pkg.Operations.var"#67#74"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String}, Pkg.Types.PackageSpec}, temp_env::String)
@ Pkg.Operations /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/Operations.jl:1701
[6] (::Pkg.Operations.var"#115#120"{Dict{String, Any}, Bool, Bool, Bool, Pkg.Operations.var"#67#74"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String}, Pkg.Types.Context, Pkg.Types.PackageSpec, String, Pkg.Types.Project, String})(tmp::String)
@ Pkg.Operations /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/Operations.jl:1790
[7] mktempdir(fn::Pkg.Operations.var"#115#120"{Dict{String, Any}, Bool, Bool, Bool, Pkg.Operations.var"#67#74"{Bool, Pkg.Types.Context, String, Pkg.Types.PackageSpec, String}, Pkg.Types.Context, Pkg.Types.PackageSpec, String, Pkg.Types.Project, String}, parent::String; prefix::String)
@ Base.Filesystem ./file.jl:760
[8] mktempdir(fn::Function, parent::String)
@ Base.Filesystem ./file.jl:756
[9] mktempdir
@ ./file.jl:756 [inlined]
[10] sandbox(fn::Function, ctx::Pkg.Types.Context, target::Pkg.Types.PackageSpec, target_path::String, sandbox_path::String, sandbox_project_override::Pkg.Types.Project; preferences::Dict{String, Any}, force_latest_compatible_version::Bool, allow_earlier_backwards_compatible_versions::Bool, allow_reresolve::Bool)
@ Pkg.Operations /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/Operations.jl:1748
[11] build_versions(ctx::Pkg.Types.Context, uuids::Set{Base.UUID}; verbose::Bool)
@ Pkg.Operations /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/Operations.jl:1134
[12] build_versions
@ /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/Operations.jl:1049 [inlined]
[13] build(ctx::Pkg.Types.Context, uuids::Set{Base.UUID}, verbose::Bool)
@ Pkg.Operations /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/Operations.jl:991
[14] build(ctx::Pkg.Types.Context, pkgs::Vector{Pkg.Types.PackageSpec}; verbose::Bool, kwargs::Base.Pairs{Symbol, Base.TTY, Tuple{Symbol}, NamedTuple{(:io,), Tuple{Base.TTY}}})
@ Pkg.API /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/API.jl:1053
[15] build(pkgs::Vector{Pkg.Types.PackageSpec}; io::Base.TTY, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
@ Pkg.API /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/API.jl:156
[16] build(pkgs::Vector{Pkg.Types.PackageSpec})
@ Pkg.API /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/API.jl:145
[17] #build#85
@ /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/API.jl:144 [inlined]
[18] build
@ /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/API.jl:144 [inlined]
[19] #build#84
@ /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/API.jl:143 [inlined]
[20] build(pkg::String)
@ Pkg.API /usr/local/lib/julia-1.9.2/share/julia/stdlib/v1.9/Pkg/src/API.jl:143
[21] top-level scope
@ REPL[5]:1