I’m in the exact same situation, followed the exact same steps, and had the same issue.
What worked for me was:
Uninstalling:
sudo service mongod stop
sudo apt-get purge "mongodb-org*"
Do NOT remove data directories – all your data will be lost if you do.
Don’t forget the quotes to prevent shell from interpreting.
Note: Calling sudo apt-get purge "mongodb-org*" deletes the mongod.conf file. In case you want to keep this file after the update, make sure you create a backup copy of it and use it after the new version has been installed.
Then install mongodb with:
sudo apt-get install -y mongodb-org
This assumes that you’ve already performed the previous installation steps (importing the public key, creating a list file, reloading local package database) as you’ve stated.