My game has an always sensor connected to a sound actuator that plays the background music. After dying, you have the option to restart (which uses a basic game actuator restart). After restarting, the background music doesn't play that time around, even though all other sounds play fine. (the background music logic bricks are connected to the character btw)
I don't seem to be experiencing the same issues as you are. Maybe try putting the logic onto the camera or another object. Alternatively, you can enable early execution of the controller to make sure it's activating before it gets interrupted.
*woops! I forgot to embed my obnoxious screeching sound I was using instead of music in the blend file. You'll have to attach your own to the logic brick located on tha camera.