Found and fixed in dev and stable. The linkcache entries weren't being cleared from memcached, so subsequent visits would pick up the wrong stored page id number and get very very confused, leading to the appearence that the move failed or that both the old and new titles apply to the page.
I've added LinkCache::clearLink() and called it from the move page functions to keep things clean.
-- brion vibber (brion @ pobox.com)