Google Play Services: Client must have ACCESS_FINE_LOCATION permission to request PRIORITY_HIGH_ACCURACY locations

Question

I am getting the error below for my Android project following this tutorial: http://blog.teamtreehouse.com/beginners-guide-location-android explaning how to use the Google Map API included in Google Play Services.

I've searched the net, and people use to say that I should add the lines

<uses-permission android:name="android.permission.ACCESS_COARSE_LOCATION" />
<uses-permission android:name="android.permission.ACCESS_FINE_LOCATION" 

to my project, but as seen below they're already there.

The error is most likely caused by the following code:

mLocationRequest = LocationRequest.create()
        .setPriority(LocationRequest.PRIORITY_HIGH_ACCURACY)
        .setInterval(10 * 1000)
        .setFastestInterval(1 * 1000);

Would could be the reason for my error?

09-14 16:33:32.913    2417-2417/com.example.nicolaslykke.myapplication E/AndroidRuntime﹕ FATAL EXCEPTION: main
    Process: com.example.nicolaslykke.myapplication, PID: 2417
    java.lang.SecurityException: Client must have ACCESS_FINE_LOCATION permission to request PRIORITY_HIGH_ACCURACY locations.
            at android.os.Parcel.readException(Parcel.java:1599)
            at android.os.Parcel.readException(Parcel.java:1552)

Here is my AndroidManifest.xml:

<?xml version="1.0" encoding="utf-8"?>
<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.example.nicolaslykke.myapplication" >

    <uses-permission android:name="android.permission.INTERNET" />
    <uses-permission android:name="android.permission.ACCESS_NETWORK_STATE" />
    <uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE" />
    <uses-permission android:name="com.google.android.providers.gsf.permission.READ_GSERVICES" />
    <!--
 The ACCESS_COARSE/FINE_LOCATION permissions are not required to use
         Google Maps Android API v2, but are recommended.
    -->
    <uses-permission android:name="android.permission.ACCESS_COARSE_LOCATION" />
    <uses-permission android:name="android.permission.ACCESS_FINE_LOCATION" />

    <application
        android:allowBackup="true"
        android:icon="@mipmap/ic_launcher"
        android:label="@string/app_name"
        android:theme="@style/AppTheme" >
        <meta-data
            android:name="com.google.android.gms.version"
            android:value="@integer/google_play_services_version" />
        <meta-data
            android:name="com.google.android.maps.v2.API_KEY"
            android:value="@string/google_maps_key" />

        <activity
            android:name=".MapsActivity"
            android:label="@string/title_activity_maps" >
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />

                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
    </application>
</manifest>