Don't believe the same app and location is being discussed here.
@rykr are all your issues in the web client?
No. I just went upstairs and did some tests on my shield. Here is what I saw.
Long pressing on an item in the live tv -> recordings page does *not* include a delete option. I have to click on an item and look at the page for that episode. I then choose the delete button. Clicking it I get the message immediately that it is taking longer than expected. After about 5 seconds or so it is deleted and I'm taken back out to the live tv -> recordings view as expected. This works ok except for the weird dialog I've already mentioned.
Going into the recordings (dvr) library things are different. Long press on an item in there and a delete option *is* include. Choosing that delete option again shows me the "slow" dialog instantly. this time the delete is very fast (< 1 sec). But the screen does not refresh. The item I just deleted is still there. I have to go back out and back in to see that it's actually gone.