If you're running an up-to-date version of memcached (1.4.4) and a recent PECL memcache extension, you may encounter difficulties deleting cached keys. See here: http://www.php.net/manual/en/function.memcache-delete.php#94536. Be sure to read the comments as there is a lot of useful information regarding the issue.
To see if you are affected run memcached in -vvv mode and look out for this:
CLIENT_ERROR bad command line format. Usage: delete <key> [noreply]
This causes magento to throw an exception with the message ""can't get stat from localhost:11211".
The problem is down to a change in behaviour of memcache in version 1.4 where they removed the second parameter passed to the delete function. See here for more info http://code.google.com/p/memcached/wiki/ReleaseNotes144. 1.4.4 thankfully added some backwards compatibility.
Magento 1.4 uses Zend Framework 1.9.6 and this, sadly, does not support these changes. Version 1.10.3+ does.