didReceiveRemoteNotification:fetchCompletionHandler not being called when app is in background and not connected to Xcode

There could be number of things might have gone wrong, The first from my own experience. In order to make silent push notification work. Your payload has to be structured correctly,

{
    "aps" : {
        "content-available" : 1
    },
    "data-id" : 345
}

Does your push message has content-available: 1 if not then iOS will not call the new delegate method.

- (void) application:(UIApplication *)application didReceiveRemoteNotification:(NSDictionary *)userInfo fetchCompletionHandler:(void (^)(UIBackgroundFetchResult))completionHandler

Possible reason is that Background App Refresh is off on your iPhone.
You can turn this option on/off in Settings->General->Background App Refresh.
When Background App Refresh is off on your phone, didReceiveRemoteNotification:fetchCompletionHandler method will be called only when the phone is connected to XCode.

Just want to add an updated answer.

I am facing the same problem.

-(void)application:(UIApplication *)application didReceiveRemoteNotification:(NSDictionary *)userInfo fetchCompletionHandler:(void (^)(UIBackgroundFetchResult))completionHandler;

Doesn't get called when the app is killed from background multitasking (double tap home button and swipe up to kill app).

I have tested this myself using development push notification and NWPusher tool (https://github.com/noodlewerk/NWPusher)

Outdated documentation

This previous block of documentation which says:

Unlike the application:didReceiveRemoteNotification: method, which is called only when your app is running, the system calls this method regardless of the state of your app. If your app is suspended or not running, the system wakes up or launches your app and puts it into the background running state before calling the method. If the user opens your app from the system-displayed alert, the system calls this method again so that you know which notification the user selected.

Is outdated (at the time of writing this 04/06/2015).

Updated Documentation (as at of 04/06/2015)

I checked the documentation (at the time of writing this 04/06/2015), it says:

Use this method to process incoming remote notifications for your app. Unlike the application:didReceiveRemoteNotification: method, which is called only when your app is running in the foreground, the system calls this method when your app is running in the foreground or background. In addition, if you enabled the remote notifications background mode, the system launches your app (or wakes it from the suspended state) and puts it in the background state when a remote notification arrives. However, the system does not automatically launch your app if the user has force-quit it. In that situation, the user must relaunch your app or restart the device before the system attempts to launch your app automatically again.

https://developer.apple.com/library/ios/documentation/UIKit/Reference/UIApplicationDelegate_Protocol/index.html#//apple_ref/occ/intfm/UIApplicationDelegate/application:didReceiveRemoteNotification:fetchCompletionHandler:

If you read carefully, you'll notice it now says:

the system calls this method when your app is running in the foreground or background.

NOT:

regardless of the state of your app

So it looks like from iOS 8+ we're out of luck :(