Ubuntu Mydomain.pem : Permission denied

Could you run

sudo -s
id

And post the output? I want to see if it's actually making you the user you think.

Also, try

sudo cat /etc/sudoers

The output of id here is quite enlightening. When you ran sudo -s, you were given a UID of 1, while the only UID that the kernel will recognize as having root privileges is UID 0.

Try running

getent passwd | grep ':0:'

and see if any entries have that 0 in their first numeric field, the UID. Whatever account that is is the real superuser on the system, while root is a fake. Once you know the name, you can try

sudo -s -u username

to get a shell as that user.

You should also post the output of

getent passwd root

The bigger issue here is how such a condition came to pass.

Is this machine offering any network services? If so, someone may have broken into it and taken it over. In that case, you should probably back up the data, do a clean re-install, and audit anything that goes back on it.

If it's more of a personal machine, might there be a knowledgeable prankster who's had access to it recently?

Edit: your comment to another answer suggests that this is a server. I would highly recommend taking it offline ASAP and imaging its disks for forensic purposes. Unless you can identify a benign cause for this in short order, you've probably had your server cracked.

Ok after some trial and error I found the solution.

I needed to add the commands XRMD and XMKD to those allowed by the user. They are described as X-Variants of the commands RMD and MKD and are apparently "often missing from a thorough configuration" according to http://www.castaglia.org/proftpd/doc/contrib/ProFTPD-mini-HOWTO-Limit.html

So perhaps somewhere in my system these commands are now being used instead.

The end of my config now reads:

<Directory /home/userftp/upload>
Umask 022 022
AllowOverwrite on
    <Limit READ>
        DenyAll
        </Limit>

        <Limit STOR CWD MKD RMD DELE XRMD XMKD>
        AllowAll
        </Limit>
</Directory>