How are you testing the background agent? Emulator or Device. Either way, you need to make sure you're not testing on a low memory 'device'.
On low memory devices (256mb), background agents are disabled. Unfortunately, the error thrown is the same as when the maximum number of agents are scheduled, i.e. "BNS Error: The maximum number of ScheduledActions of this type have already been added."