[SalesForce] Salesforce REST API with PHP, INVALID_SESSION_ID after successful authentication

I connected my web app to salesforce and successfully followed all the steps in the web server OAuth flow to get an access_token and related info:
https://developer.salesforce.com/docs/atlas.en-us.api_placeorder.meta/api_placeorder/intro_understanding_web_server_oauth_flow.htm

Every step seems to return the expected set of results specified in the docs, but when I try to make requests with the final access token, I get an error saying my session ID is invalid. Here is my code:

    // Execute a request for access_token and related info
    $output = json_decode(curl_exec($ch));
    $info = curl_getinfo($ch);
    curl_close($ch);

    // Display output and curl info
    var_dump($info);
    var_dump($output);

    // Extract token and instance_url from output
    $sf_url = $output->instance_url . '/services/data/v35.0/';
    $sf_auth = 'Bearer ' . $output->access_token;

    // Execute a new cURL request with auth values
    $ci = curl_init();
    curl_setopt($ci, CURLOPT_URL, $sf_url);
    curl_setopt($ci, CURLOPT_RETURNTRANSFER, true);
    curl_setopt($ci, CURLINFO_HEADER_OUT, true);
    curl_setopt($ci, CURLOPT_HTTPGET, true);
    curl_setopt($ci, CURLOPT_HTTPHEADER, array(
        'Accept' => 'application/json',
        'Authorization' => $sf_auth,
        'X-PrettyPrint' => 1
    ));

    $output2 = curl_exec($ci);
    $info2 = curl_getinfo($ci);
    curl_close($ci);

    // Display output and curl info
    var_dump($info2);
    var_dump($output2);

The dump from $output gives:

object(stdClass)#194 (7) { 
["access_token"]=> string(112) "xxxxxxxxxxxxxxxx" 
["signature"]=> string(44) "xxxxxxxxxxxxxx" 
["scope"]=> string(3) "api" 
["instance_url"]=> string(27) "https://cs10.salesforce.com" 
["id"]=> string(68) "https://test.salesforce.com/id/xxxxx/xxxxx"
["token_type"]=> string(6) "Bearer" 
["issued_at"]=> string(13) "1453358xxxxxx" }

The dump from $output2 gives:

string(75) "[{"message":"Session expired or invalid","errorCode":"INVALID_SESSION_ID"}]"

Any help here would be much appreciated.

* UPDATE *

I also tried using the username-password auth flow, and I'm getting the same result. I can get an access token, but I can't query the database, and the error being returned is the same INVALID_SESSION_ID.

I used the Postman plugin for chrome, passed in all the same info for the username-password flow, and it works for making queries. I'm not sure what is being done differently, seems like all the data being passed is the same.

* Update 2 *

The dumps from curl_getinfo() show that the headers aren't being set in the second curl request, but I can't see why.

The var_dump from $info gives:

array(27) { 
["url"]=> string(294) "https://test.salesforce.com/services/oauth2/token?client_id=xxxxxxx&client_secret=xxxxxxxx&username=xxxxxxxx&password=xxxxxxxx&grant_type=password" 
["content_type"]=> string(30) "application/json;charset=UTF-8" 
["http_code"]=> int(200) 
["header_size"]=> int(669) 
["request_size"]=> int(396) 
["filetime"]=> int(-1) 
["ssl_verify_result"]=> int(0) 
["redirect_count"]=> int(0) 
["total_time"]=> float(0.602597) 
["namelookup_time"]=> float(0.028403) 
["connect_time"]=> float(0.097796) 
["pretransfer_time"]=> float(0.241315) 
["size_upload"]=> float(0) 
["size_download"]=> float(361) 
["speed_download"]=> float(599) 
["speed_upload"]=> float(0) 
["download_content_length"]=> float(-1) 
["upload_content_length"]=> float(-1) 
["starttransfer_time"]=> float(0.601087) 
["redirect_time"]=> float(0) 
["redirect_url"]=> string(0) "" 
["primary_ip"]=> string(14) "xx.xx.xx.xx" 
["certinfo"]=> array(0) { } 
["primary_port"]=> int(443) 
["local_ip"]=> string(11) "xx.xx.xx.xx" 
["local_port"]=> int(45269) 
["request_header"]=> string(396) "POST /services/oauth2/token?client_id=xxxxxxxxxxx&client_secret=xxxxxxxxx&username=xxxxxx&password=xxxxxx&grant_type=password HTTP/1.1 Host: test.salesforce.com Accept: */* Content-Type: application/x-www-form-urlencoded Expect: 100-continue " }

The dump from $info2 gives:

array(27) { 
["url"]=> string(47) "https://cs10.salesforce.com/services/data/v35.0" 
["content_type"]=> string(30) "application/json;charset=UTF-8" 
["http_code"]=> int(401) 
["header_size"]=> int(319) 
["request_size"]=> int(77) 
["filetime"]=> int(-1) 
["ssl_verify_result"]=> int(0) 
["redirect_count"]=> int(0) 
["total_time"]=> float(0.278246) 
["namelookup_time"]=> float(0.060541) 
["connect_time"]=> float(0.095554) 
["pretransfer_time"]=> float(0.170015) 
["size_upload"]=> float(0) 
["size_download"]=> float(75) 
["speed_download"]=> float(269) 
["speed_upload"]=> float(0) 
["download_content_length"]=> float(-1) 
["upload_content_length"]=> float(0) 
["starttransfer_time"]=> float(0.20641) 
["redirect_time"]=> float(0) 
["redirect_url"]=> string(0) "" 
["primary_ip"]=> string(12) "xx.xx.xx.xx" 
["certinfo"]=> array(0) { } 
["primary_port"]=> int(443) 
["local_ip"]=> string(11) "xx.xx.xx.xx" 
["local_port"]=> int(50733) 
["request_header"]=> string(77) "GET /services/data/v35.0 HTTP/1.1 Host: cs10.salesforce.com Accept: */* " }