sudo: effective uid is not 0, is /usr/bin/sudo on a file system with the 'nosuid' option set or an NFS file system without root privileges?

Question

I've been using cronopete and timeshift to do my backups on Pop!_OS. cronopete for just /home and timeshift for the entire system.

I put in a new m.2 NVMe drive hoping I could just restore the timeshift backup to the blank drive, but this turned out not to be the case.

I ultimately had to reinstall everything into a clean install of Pop!_OS and then just copied the /home backup over from cronopete.

It seemed like it mostly worked, but now I'm trying to do sudo apt install python3-virtualenv and I'm getting the error:

sudo: effective uid is not 0, is /usr/bin/sudo on a file system with the 'nosuid' option set or an NFS file system without root privileges?

I came across the following, but it still isn't helping me in resolving the issue. Not quite sure what I need to do.

https://www.sudo.ws/troubleshooting.html

Q) Sudo compiles and installs OK but when I try to run it I get:
    effective uid is not 0, is /usr/local/bin/sudo on a file system with the
    'nosuid' option set or an NFS file system without root privileges?

A) The owner and permissions on the sudo binary appear to be OK but when
   sudo ran, the setuid bit did not have an effect.  There are two common
   causes for this.  The first is that the file system the sudo binary
   is located on is mounted with the 'nosuid' mount option, which disables
   setuid binaries.  The output of the "mount" command should tell you if
   the file system is mounted with the 'nosuid' option.  The other possible
   cause is that sudo is installed on an NFS-mounted file system that is
   exported without root privileges.  By default, NFS file systems are
   exported with uid 0 mapped to a non-privileged uid (usually -2).  You
   should be able to determine whether sudo is located on an NFS-mounted
   filesystem by running "df `which sudo`".

The outputs for two commands it suggests running are the following:

$ mount          
sysfs on /sys type sysfs (rw,nosuid,nodev,noexec,relatime)
proc on /proc type proc (rw,nosuid,nodev,noexec,relatime)
udev on /dev type devtmpfs (rw,nosuid,noexec,relatime,size=32835804k,nr_inodes=8208951,mode=755)
devpts on /dev/pts type devpts (rw,nosuid,noexec,relatime,gid=5,mode=620,ptmxmode=000)
tmpfs on /run type tmpfs (rw,nosuid,nodev,noexec,relatime,size=6576088k,mode=755)
/dev/nvme0n1p3 on / type ext4 (rw,noatime,errors=remount-ro)
securityfs on /sys/kernel/security type securityfs (rw,nosuid,nodev,noexec,relatime)
tmpfs on /dev/shm type tmpfs (rw,nosuid,nodev)
tmpfs on /run/lock type tmpfs (rw,nosuid,nodev,noexec,relatime,size=5120k)
tmpfs on /sys/fs/cgroup type tmpfs (ro,nosuid,nodev,noexec,mode=755)
cgroup2 on /sys/fs/cgroup/unified type cgroup2 (rw,nosuid,nodev,noexec,relatime,nsdelegate)
cgroup on /sys/fs/cgroup/systemd type cgroup (rw,nosuid,nodev,noexec,relatime,xattr,name=systemd)
pstore on /sys/fs/pstore type pstore (rw,nosuid,nodev,noexec,relatime)
efivarfs on /sys/firmware/efi/efivars type efivarfs (rw,nosuid,nodev,noexec,relatime)
none on /sys/fs/bpf type bpf (rw,nosuid,nodev,noexec,relatime,mode=700)
cgroup on /sys/fs/cgroup/devices type cgroup (rw,nosuid,nodev,noexec,relatime,devices)
cgroup on /sys/fs/cgroup/net_cls,net_prio type cgroup (rw,nosuid,nodev,noexec,relatime,net_cls,net_prio)
cgroup on /sys/fs/cgroup/cpu,cpuacct type cgroup (rw,nosuid,nodev,noexec,relatime,cpu,cpuacct)
cgroup on /sys/fs/cgroup/hugetlb type cgroup (rw,nosuid,nodev,noexec,relatime,hugetlb)
cgroup on /sys/fs/cgroup/freezer type cgroup (rw,nosuid,nodev,noexec,relatime,freezer)
cgroup on /sys/fs/cgroup/blkio type cgroup (rw,nosuid,nodev,noexec,relatime,blkio)
cgroup on /sys/fs/cgroup/pids type cgroup (rw,nosuid,nodev,noexec,relatime,pids)
cgroup on /sys/fs/cgroup/rdma type cgroup (rw,nosuid,nodev,noexec,relatime,rdma)
cgroup on /sys/fs/cgroup/perf_event type cgroup (rw,nosuid,nodev,noexec,relatime,perf_event)
cgroup on /sys/fs/cgroup/memory type cgroup (rw,nosuid,nodev,noexec,relatime,memory)
cgroup on /sys/fs/cgroup/cpuset type cgroup (rw,nosuid,nodev,noexec,relatime,cpuset)
systemd-1 on /proc/sys/fs/binfmt_misc type autofs (rw,relatime,fd=28,pgrp=1,timeout=0,minproto=5,maxproto=5,direct,pipe_ino=21104)
mqueue on /dev/mqueue type mqueue (rw,nosuid,nodev,noexec,relatime)
hugetlbfs on /dev/hugepages type hugetlbfs (rw,relatime,pagesize=2M)
debugfs on /sys/kernel/debug type debugfs (rw,nosuid,nodev,noexec,relatime)
tracefs on /sys/kernel/tracing type tracefs (rw,nosuid,nodev,noexec,relatime)
fusectl on /sys/fs/fuse/connections type fusectl (rw,nosuid,nodev,noexec,relatime)
configfs on /sys/kernel/config type configfs (rw,nosuid,nodev,noexec,relatime)
/dev/nvme0n1p1 on /boot/efi type vfat (rw,relatime,fmask=0077,dmask=0077,codepage=437,iocharset=iso8859-1,shortname=mixed,errors=remount-ro)
/dev/nvme0n1p2 on /recovery type vfat (rw,relatime,fmask=0077,dmask=0077,codepage=437,iocharset=iso8859-1,shortname=mixed,errors=remount-ro)
tmpfs on /run/user/110 type tmpfs (rw,nosuid,nodev,relatime,size=6576084k,mode=700,uid=110,gid=116)
gvfsd-fuse on /run/user/110/gvfs type fuse.gvfsd-fuse (rw,nosuid,nodev,relatime,user_id=110,group_id=116)
vmware-vmblock on /run/vmblock-fuse type fuse.vmware-vmblock (rw,nosuid,nodev,relatime,user_id=0,group_id=0,default_permissions,allow_other)
tmpfs on /run/user/1000 type tmpfs (rw,nosuid,nodev,relatime,size=6576084k,mode=700,uid=1000,gid=1000)
gvfsd-fuse on /run/user/1000/gvfs type fuse.gvfsd-fuse (rw,nosuid,nodev,relatime,user_id=1000,group_id=1000)
/dev/fuse on /run/user/1000/doc type fuse (rw,nosuid,nodev,relatime,user_id=1000,group_id=1000)
/dev/sda2 on /media/work/Linux Partition type ext4 (rw,nosuid,nodev,relatime,uhelper=udisks2)
/dev/sda1 on /media/work/Windows Backups type fuseblk (rw,nosuid,nodev,relatime,user_id=0,group_id=0,default_permissions,allow_other,blksize=4096,uhelper=udisks2)

$ df `which sudo`
Filesystem     1K-blocks     Used Available Use% Mounted on
/dev/nvme0n1p3 482446164 77649084 380220452  17% /

Any suggestions for how to resolve this?

Solution

Ok, this seems to have fixed it. Largely based on an answer found here:

https://stackoverflow.com/questions/16682297/getting-message-sudo-must-be-setuid-root-but-sudo-is-already-owned-by-root/19306929#19306929

1. Hold space when booting Pop!_OS
2. Select Recovery, which brings up the OS installer
3. SUPER + T to bring up terminal
4. sudo -i to switch to root
5. mount -o remount,rw /
6. mount --all
7. chown root:root /usr/bin/sudo
8. chmod 4755 /usr/bin/sudo
9. Restart Pop!_OS and login normally

Now I am able to run sudo commands such as sudo apt install python3-virtualenv without issues... so far.