Ubuntu 22.04, Intel Xeon E5-2640 v3, getting "Illegal instruction" and "core dumped" error from apt

I have Ubuntu 22.04 Server, running on Intel(R) Xeon(R) CPU E5-2640 v3 @ 2.60GHz

When trying to install packages apt complains about unment dependencies and suggests running apt --fix-broken install:

# apt install vim
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
You might want to run 'apt --fix-broken install' to correct these.
The following packages have unmet dependencies:
 libpam-modules : PreDepends: libpam-modules-bin (= 1.4.0-11ubuntu2) but 1.4.0-11ubuntu2.1 is to be installed
 vim : Depends: vim-runtime (= 2:8.2.3995-1ubuntu2.3) but it is not going to be installed
       Depends: libsodium23 (>= 1.0.14) but it is not going to be installed

But when I do run it, I'm always getting Illegal instruction & a core dump

# apt --fix-broken install
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
Correcting dependencies... Done
The following additional packages will be installed:
  libpam-modules libpam-modules-bin
The following packages will be upgraded:
  libpam-modules libpam-modules-bin
2 upgraded, 0 newly installed, 0 to remove and 98 not upgraded.
7 not fully installed or removed.
Need to get 318 kB of archives.
After this operation, 0 B of additional disk space will be used.
Do you want to continue? [Y/n] 
Get:1 http://pl.archive.ubuntu.com/ubuntu jammy-updates/main amd64 libpam-modules-bin amd64 1.4.0-11ubuntu2.3 [37.6 kB]
Get:2 http://pl.archive.ubuntu.com/ubuntu jammy-updates/main amd64 libpam-modules amd64 1.4.0-11ubuntu2.3 [280 kB]
Fetched 318 kB in 0s (1,959 kB/s)       
Illegal instruction (core dumped)
(Reading database ... 144899 files and directories currently installed.)
Preparing to unpack .../libpam-modules-bin_1.4.0-11ubuntu2.3_amd64.deb ...
Unpacking libpam-modules-bin (1.4.0-11ubuntu2.3) over (1.4.0-11ubuntu2.1) ...
Setting up libpam-modules-bin (1.4.0-11ubuntu2.3) ...
(Reading database ... 144899 files and directories currently installed.)
Preparing to unpack .../libpam-modules_1.4.0-11ubuntu2.3_amd64.deb ...
dpkg: error processing archive /var/cache/apt/archives/libpam-modules_1.4.0-11ubuntu2.3_amd64.deb (--unpack):
 new libpam-modules:amd64 package pre-installation script subprocess was killed by signal (Illegal instruction), core dumped
Errors were encountered while processing:
 /var/cache/apt/archives/libpam-modules_1.4.0-11ubuntu2.3_amd64.deb
needrestart is being skipped since dpkg has failed
E: Sub-process /usr/bin/dpkg returned an error code (1)

Interestingly, some other programs are not working too, throwing Illegal Instruction errror, for example:

# man
man: c!n'�(mxol Ehe(manpath coJfigura4i/n gilG +eTc/�enpiticon`ig
Illegal instruction (core dumped)

I tried to search for solutions on the internet, but there's almost no info. All cases where people see "illegal instruction" are when they're trying to run a code they compiled incorrectly (like targetting wrong CPU architecture). But here I'm just trying to run some binaries provided by public Ubuntu repository on a rather common Intel CPU. What is going on? Can a corrupted filesystem produce this type of errors (like, a physical disk damage)? Or is it CPU-related?

My lscpu:

Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         46 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  32
  On-line CPU(s) list:   0-31
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Xeon(R) CPU E5-2640 v3 @ 2.60GHz
    CPU family:          6
    Model:               63
    Thread(s) per core:  2
    Core(s) per socket:  8
    Socket(s):           2
    Stepping:            2
    CPU max MHz:         3400.0000
    CPU min MHz:         1200.0000
    BogoMIPS:            5200.49
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonst
                         op_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_f
                         ault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid cqm xsaveopt cqm_llc cqm_occup_llc dtherm ida arat pln pts md_clea
                         r flush_l1d
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   512 KiB (16 instances)
  L1i:                   512 KiB (16 instances)
  L2:                    4 MiB (16 instances)
  L3:                    40 MiB (2 instances)
NUMA:                    
  NUMA node(s):          2
  NUMA node0 CPU(s):     0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30
  NUMA node1 CPU(s):     1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31
Vulnerabilities:         
  Itlb multihit:         KVM: Mitigation: VMX disabled
  L1tf:                  Mitigation; PTE Inversion; VMX conditional cache flushes, SMT vulnerable
  Mds:                   Mitigation; Clear CPU buffers; SMT vulnerable
  Meltdown:              Mitigation; PTI
  Mmio stale data:       Mitigation; Clear CPU buffers; SMT vulnerable
  Retbleed:              Not affected
  Spec store bypass:     Mitigation; Speculative Store Bypass disabled via prctl and seccomp
  Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:            Mitigation; Retpolines, IBPB conditional, IBRS_FW, STIBP conditional, RSB filling, PBRSB-eIBRS Not affected
  Srbds:                 Not affected
  Tsx async abort:       Not affected

OS:

Distributor ID: Ubuntu
Description:    Ubuntu 22.04.1 LTS
Release:    22.04
Codename:   jammy