ReferenceError: GM_xmlhttpRequest is not defined

I had the same problem, and what fixed it for me was adding this at the top:

// @grant        GM_xmlhttpRequest

Since the news version (GM 4.0) this error happened when you use GM_xmlhttpRequest because GM_xmlhttpRequest was replaced by : GM.xmlHttpRequest.

The new code is :

// ==UserScript==
// @name          ...
// @namespace     ...
// @description   ...
// @include       ...
// @grant         GM.xmlHttpRequest
// ==/UserScript==

console.log(GM_info);
try
{
    console.log(GM.xmlHttpRequest({ method: "GET", url: "http://google.ca/", synchronous: true }).readyState);
}
catch (e)
{
    console.log(e);
}
//...

Greasemonkey: "GM_xmlhttpRequest is not defined" with the new update

Reinstalling the script fixed the problem. I didn't need to restart Firefox, but it may be helpful for other people. Brock's answer has helpful debugging tips for problems like this.