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, $query_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' => $token,
            '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: */* " }