Is it not working at all or is it just not deleting? In other words, when you press it the first time are you getting a delete confirmation message or simply nothing? Can you use the Delete option in the playback menu to delete selectively or by date?
If the button pops up the delete confirmation message but a second press doesn't delete it, and you can't delete selectively through the Delete option in the playback menu then I'd suggest reformatting the card in the camera and trying again. No reason other than a hunch.