My guess is that you're not clicking the check box on the person that you want to deny... When you click on your notification, it will give you the option to accept or deny the request. You have to put a check mark on the box next to the persons avatar for it to accept or deny it, otherwise, you've accepted/denied nothing.
"What, exactly, is the internet? Basically it is a global network exchanging digitized data in such a way that any computer, anywhere, that is equipped with a device called a 'modem', can make a noise like a duck choking on a kazoo." - Dave Barry