In my case, I had previously set the session to inactive between song changes before starting a new song:
AudioSessionSetActive(false);
Once I removed this AudioQueueStart works just fine from the background.
Please let me know more about AudioQueueStart, is there any method instead of AudioQueueStart?