Ran into this issue while setting up an EC2 instance. My ssh session was interrupted while having done sudo visudo. I couldn’t access the file anymore, nor delete the related .tmp.
I found my solution in the comments here.
ps -ef|grep sudo
sudo kill -9 replace-with-visudo-process-nr
Repeat this for each process containing visudo. Afterwards I was able to sudo visudo again.