Finally, I've solved it!
The quick version:
Running php-fpm on ubuntu:
sudo nano /etc/php5/conf.d/apc.ini
You should see:
paste in the below lines:
save and close.
If you've got limited memory, you could try:
service php5-fpm restart.
Now go to your Wordpress admin and watch that sucker fly with near instant response.
The long version
I was so damn sick of this slow admin I just decided to keep going, trying stuff.
Finally, I came across this post:
which led me to this post:
and finally this:
The key to this was "download http://pecl.php.net/get/APC extract and run the apc.php, there you have a nice diagram how your cache usage look like"
It showed APC was completely using its tiny default 32Mb, and was 100% fragmented. I've been running it for an hour, and see
Hits: 70874 (98.6%) Misses: 991 (1.4%) Used: 124.4 MBytes (63.5%) Fragmentation: 0.00%
Before this tweak it was something like 70% misses and 100% fragmentation. No wonder Wordpress was running slow!