EDIT: Disabling database cached fixed it, the object cache is fine. I guess it's not recommended to have both DB and object cache enabled at the same time anyway?
Upgrading to the latest W3TC has resulted in extremely odd performance with memcached enabled on object / database queries. I'm seeing first access times of 11 seconds on some pages. It's fast after the cache has been primed, but here's the thing: accessing the same pages with the cache completely disabled load in < 1 sec. Any ideas?