Try this version:

function $x(p, context) {
      	if (!context) context = document;
      	var i, arr = [], xpr = document.evaluate(p, context, null, 6, null);
      	for (i=0; item=xpr.snapshotItem(i); i++) arr.push(item);
      	return arr;
      }
      
      var links = $x("//a[contains(@href, 'imdb.com/title/')]");
      if (links.length) {
      	links.forEach(function(link,i) {
      	if (!link.hasChildNodes()) {
      			if (!GM_getValue(link.href)) {
      				GM_xmlhttpRequest({
      					method: "get",
      					url: link.href,
      					onload: rs(i)
      				});
      			}
      		}
      	});
      }
      function rs(i) {
      	return function(e) {
      		var title = e.responseText.split("<title>")[1].split("</title>")[0];
      		links[i].textContent = title;
      		GM_setValue(links[i].href, title);
      	}
      }

This is just alpha, I haven't tried it yet.

I updated the script so image links won't be changed.

Updated the script a little.
If the link has been changed before it will be saved, making the script work a lot faster.

Also, http://*.imdb.com will be excluded.
Thanks for the tip, Hiromacu.