Just to add - your assumption that is was not your server turned out to be wrong. You have horribly slow disk IO. This is typical for VMs where the physical disk is remote and/or a file somewhere.
A server with fast, local disks would also solve your problem if that sounds like a better idea - although setting up memcached isn't too difficult.
Also consider Redis instead of memcached. There is some talk of memcached no longer being developed - I'm not sure how true this is.