rm: cannot remove '/boot/initrd.img-*': Structure needs cleaning

Question

My Ubuntu 20.04 laptop somehow got into a state where apt update no longer works. Instead, running that gives the output:

Removing linux-image-5.4.0-73-generic (5.4.0-73.82~18.04.1) ...
/etc/kernel/postrm.d/initramfs-tools:
update-initramfs: Deleting /boot/initrd.img-5.4.0-73-generic
rm: cannot remove '/boot/initrd.img-5.4.0-73-generic': Structure needs cleaning
dkpg: error processing package linux-image.5.4.0-73-generic (--remove):
 installed linux-image-5.4.0-73-generic package post-removal script subprocess returned error exist status 1
Errors were encountered while processing:
 linux-image-5.4.0-73-generic
E: Sub-process /usr/bin/dpkg returned an error code (1)

Tried the following but the problem persists.

sudo dpkg --configure -a
sudo apt-get install --fix-broken  # gives the same error
sudo apt clean
sudo apt autoremove                # gives the same error

What else can we try? Thanks!

---

lsblk Output:

nvme0n1      259:0    0   477G  0 disk  
├─nvme0n1p1  259:1    0   976M  0 part  /boot
├─nvme0n1p2  259:2    0   7.6G  0 part  
│ └─encr_sd1 253:1    0   7.6G  0 crypt [SWAP]
├─nvme0n1p3  259:3    0   477M  0 part  /boot/efi
└─nvme0n1p4  259:4    0 467.9G  0 part  
  └─encr_sd0 253:0    0 467.9G  0 crypt /