Authentication token manipulation error after upgrade from 16.04 -> 18.04 -> 20.04

Introduction

I recently upgraded the Ubuntu release from 16.04 to 18.04 to 20.04 and after completing the upgrades and fixing outstanding issues with apps that were running on that local development server I noticed the passwd command to change user passwords has stopped working.

What is the error

Here is what happens when I attempt to change my own user's password

joe@machine1:/etc$ passwd
Changing password for joe.
Current password: 
passwd: Authentication token manipulation error
passwd: password unchanged

Here is what happens when I attempt to change another user's password

root@machine1:/etc# passwd openvpn
passwd: Authentication token manipulation error
passwd: password unchanged

Here is what I tried until now

Here are my attempts after looking at different solutions online.

• I have tried rebooting the system
• I have tried remounting the FS as read,write using this command mount -o remount,rw /
• I have tried using pam-auth-update
• I have checked the permissions on the following files:
  • -rw-r--r-- 1 root root 3790 Aug 17 12:45 /etc/passwd
  • -rw-r----- 1 root shadow 2674 Aug 17 13:41 /etc/shadow
  • -rwsr-xr-x 1 root root 68208 Jul 14 19:08 /usr/bin/passwd
• I have made sure that there was sufficient space on my filesystem. There is ~300GB free so I don't think that is part of the issue.
• I have used pwck which did not really help, here is the output of that command

  user 'lp': directory '/var/spool/lpd' does not exist
  user 'news': directory '/var/spool/news' does not exist
  user 'uucp': directory '/var/spool/uucp' does not exist
  user 'list': directory '/var/list' does not exist
  user 'irc': directory '/var/run/ircd' does not exist
  user 'gnats': directory '/var/lib/gnats' does not exist
  user 'nobody': directory '/nonexistent' does not exist
  user 'openvpn': directory '/home/openvpn' does not exist
  user 'openvpn': program '/sbin/nologin' does not exist
  pwck: no changes
  

Any ideas what could be done to fix this issue. I can confirm that this used to work before the upgrade as I had recently added a user to the system.