REST API Seems Broken - error "All requests that modify the database must be http POST, not GET." eronously raised

Since Upgrading from 3.6 to 4.7.1 a problem occurs.

On Wordpress 4.4.2, Observed twice on a Windows and Debian Stable server.

When making a create call to the API, I get a "SECURITY: All requests that modify the database must be http POST, not GET." error.

It is a POST request - in both cases I verified so in the apache logs:

10.0.2.2 - - [15/Feb/2016:11:38:47 +0000] "POST /wp-content/plugins/civicrm/civicrm/extern/rest.php?key=xxxxxxxxxxx&api_key=xxxxxxxxxxxxxx&json=1&entity=contact&action=create&email=TEST1%40EXAMPLE.org&first_name=Test&last_name=Test1&contact_type=Individual HTTP/1.1" 200 1489 "-" "Guzzle/5.3.0 curl/7.30.0 PHP/5.4.45"

If I go into CRM/Util/REST.php and comment out:

    if ($_SERVER['REQUEST_METHOD'] == 'GET' &&
       strtolower(substr($args[2], 0, 3)) != 'get' &&
       strtolower($args[2] != 'check')) {
      // get only valid for non destructive methods
      require_once 'api/v3/utils.php';
      return civicrm_api3_create_error("SECURITY: All requests that modify the database must be http POST, not GET.",
        array(
          'IP' => $_SERVER['REMOTE_ADDR'],
          'level' => 'security',
          'referer' => $_SERVER['HTTP_REFERER'],
          'reason' => 'Destructive HTTP GET',
        )
      );
    }

It works again.

If I edit /wp-content/plugins/civicrm/civicrm/extern/rest.php and at the top put:

<?php
var_dump($_SERVER);
die();

I see:

["REQUEST_METHOD"]=>
string(4) "POST"

However if I edit the code in CRM/Util/REST.php to:

    if ($_SERVER['REQUEST_METHOD'] == 'GET' &&
       strtolower(substr($args[2], 0, 3)) != 'get' &&
       strtolower($args[2] != 'check')) {
      // get only valid for non destructive methods


      require_once 'api/v3/utils.php';
        return civicrm_api3_create_error("WTF", $_SERVER);

I see:

,"REQUEST_METHOD":"GET",

So something in CivicCRM or WordPress is changing that POST to a GET.